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