Module 12 Vocab

Question 1

Graph Isomorphism (notation)

12.1

Answer 1

G1 ≃ G2

Question 2

Graph Isomorphism (definition)

12.1

Answer 2

bijection β: V1 → V2
such that for any u1v1 ∈ V1 we have
u1—v1∈E1 iff β(u1)—β(v1)∈E2

Question 3

Graph Isomorphism (words)

12.1

Answer 3

match up the vertices based on their degree

Question 4

How to write isomorphism

12.1

Answer 4

G1 ≃ G2 by the bijection
4→5, 2→6, 3→8, 1→7

Question 5

Isomorphism Proposition I

12.1

ex path

Answer 5

any 2 complete/path/cycle/edgeless graphs are isomorphic iff they have the same number of vertices

Question 6

Isomorphism Proposition II

12.1

ex grid

Answer 6

any 2 mxn grids are isomorphic, as well as isomorphic to any nxm grids

Question 7

Isomorphism Proposition III

12.1

ex complete

Answer 7

any permutation of n vertices in Kn is n isomorphism

Question 8

Subgraph (intuitive)

12.1

Answer 8

the part of a graph that can be in its own right, a graph

Question 9

Subgraph (definition)

12.1

Answer 9

G1 is a subgraph of G2
when V1⊆V2 and E1⊆E2
if it actually makes a graph
(beware pointless edges)

Question 10

Induced Subgraphs

12.1

Answer 10

the subgraph of G induced by V’∈V
is the graph G’ = (V’, E’)
where E’ consists of all the edges of G whose endpoints are both in V’

Question 11

Counting Paths

12.1

Answer 11

to count paths of length n(edges),
count the subgraphs that are path graphs on n+1 vertices

Question 12

Paths of length 2 in Cn

12.1

Answer 12

n paths of length 2 in Cn

Question 13

Sujective

12.1

Answer 13

range = whole codomain
ex: every vertex fits some characteristic

Question 14

Bijective

12.1

Answer 14

every element maps to a distinct element
ex: only maps to one path

Question 15

Bijection Rule

12.1

Answer 15

|A| = |B|
domain = codomain

Question 16

Closed Walk

12.2

Answer 16

walk where first and last vertex are the same

Question 17

Cycle

12.2

Answer 17

closed walk of length ≥ 3 (edges)
in which all nodes are pairwise disjoint
except for the last/first

reminder: 4 nodes total for mininum 1-2-3-1

Question 18

1-2-3-4-2-1

12.2

Answer 18

closed walk
(2 twice)

Question 19

2

12.2

Answer 19

closed walk of length 0

Question 20

2-3-4-2

12.2

Answer 20

cycle length 3

Question 21

Counting Cycles

12.2

Answer 21

to count cycles of length n,
count subgraphs that are cycle graphs
on n vertices

Question 22

How many cycles are there in K4?

12.2

Answer 22

length 3: 4 choose 3
length 4: induce last node from node 1, 3 choose 2

Question 23

Cycle of length 3
(of Kn)

12.2

Answer 23

“the subgraph induced by any 3 vertices is a cycle subgraph”

n choose 3

Question 24

Cycle of length 4
(of Kn)

12.2

Answer 24

step 1: pick 4 nodes
step 2: multiply by 3 (3 choose 2)

Question 25

What is the total number of cycles in K5? | 12.2

Answer 25

37

Question 26

cc Partition | 12.3

Answer 26

cc's partition the set of vertices V as well as the set of edges E

Question 27

we can view --- as --- induced by a set of --- | 12.3

Answer 27

cc's subgraphs vertices

Question 28

Edge Partition Proposition | 12.3

Answer 28

every edge {u,v}∈E belongs to exactly one of the subgraphs induced by the cc's of G

Question 29

cc's as graphs proposition | 12.3

Answer 29

to count the # of paths/cycles of length k we add up the # of paths/cycles in each of its cc's

Question 30

Acyclic | 12.3

Answer 30

a graph in which there are no cycles

Question 31

Tree | 12.3

Answer 31

a graph that is both connected and acyclic

Question 32

Forest | 12.3

Answer 32

an acyclic graph, since all its cc's are trees

Question 33

3 Isomorphism Propositions | 12.3

Answer 33

if G1 ≃ G2, then G1 is acyclic iff G2 is acylic G1 is connected iff G2 is connected G1 is a tree iff G2 is a tree

Question 34

Edges in Trees Proposition | 12.3

Answer 34

a tree has one more vertex than edges if tree, then |E| = |V| - 1

Question 35

Edges in Forrests Corollary | 12.3

Answer 35

the sum of a forrest's edges is the difference between its nodes and cc's if forest, |E| = |V| - |CC|

Question 36

Vertices in Trees Propositions | 12.3

Answer 36

any tree with n vertices has n-1 edges

Question 37

Leaf | 12.3

Answer 37

a node of degree 1

Question 38

Leaf Lemma I | 12.3

Answer 38

every tree with edges has at least one leaf

Question 39

Leaf Lemma II | 12.3

Answer 39

removing a leaf from a tree with edges leaves again a tree | *removing a leaf means also removing its one incident edge

Question 40

Maximally Connected Tree Proposition | 12.4

Answer 40

removing any edge in a tree disconnects it

Question 41

Maximally Acyclic Tree Proposition | 12.4

Answer 41

adding an edge between any two non-adjacent vertices in a tree creates a cycle

Question 42

Unique-Path Connected Tree Proposition | 12.4

Answer 42

any two distinct vertices of a tree are connected by one unique path

Question 43

Edge in Acyclic Graph Lemma | 12.4

Answer 43

adding an edge to an acyclic graph creates at most one cycle

Question 44

Cycle in Closed Walk Lemma | 12.4

Answer 44

any closed walk of non-zero length that traverses at least one of its edges exactly once contains a cycle

Question 45

Unique Path Connectivity Proposition | 12.4

Answer 45

a graph such that any two distinct vertices are connected by a (1) unique path must be a tree

Question 46

Cut Edge | Self

Answer 46

an edge that if removed gives us a graph with strictly more cc's

Question 47

Cut Edge Proposition | Self

Answer 47

removing a cut edge increases the number of cc's by exactly 1