Module 13 Vocab

Question 1

Spanning Subgraph

13.1

Answer 1

a subgraph whose vertex set is the entire set V
(of the original graph G)

Question 2

Spanning Tree

13.1

Answer 2

of a connected graph G,
a spanning subgraph that’s also a tree

Question 3

Spanning Forest

13.1

Answer 3

a spanning tree for each of hte cc’s of G

Question 4

Spanning Tree Proposition

13.1

Answer 4

every connected graph has a spanning tree

hence every graph has a spanning forest

Question 5

Cut Edge

13.1

Answer 5

erasing it strictly increases the number of cc’s

Question 6

Cut Edge Proposition

13.1

Answer 6

removing a cut edge in a graph increases the number of cc’s by exactly one

Question 7

Edge Proposition II

13.1

Answer 7

an edge is a cut edge iff it does not belong to any cycle

every edge in a cycle is not a cut edge

Question 8

Edge Corollary

13.1

Answer 8

a connected graph is a tree iff each one of its edges is a cut edge

Question 9

Edge-Prunning Algorithm

13.1

Answer 9

1) Let T = G
2) for k = 1,…,m:
remove ek from T if it’s not a cut edge
else keep ek in T
3) Output T

Question 10

Edge-Growing Algorithm

13.1

Answer 10

1) Let T = (V, ∅)
2) For k = 1,…,m:
add ek to T if doing so doesn’t form a cycle with the edges already in T
else leave ek out of T
3) Output T

Question 11

k-coloring

13.2

Answer 11

a function
f: V→[1..k]
each vertex maps to a color

Question 12

Proper Coloring

13.2

Answer 12

when for any edge u-v we have f(u) ≠ f(v)
adjacent vertices are different colors

Question 13

k-colorable

13.2

Answer 13

a graph that admits a proper k-coloring

Question 14

what does k-colorable imply?

13.2

Answer 14

j-colorable for any j ≥ k

Question 15

n-colorable

13.2

Answer 15

a graph with n vertices is n-colorable

Question 16

Chromatic Number (notation)

13.2

Answer 16

X(G)
“chi of G”

Question 17

Chromatic Number (definition)

13.2

Answer 17

the smallest k such that G is k-colorable

Question 18

Chromatic Proposition

13.2

Answer 18

X(G) = 1 iff G is edgeless

Question 19

Chromatic Path Graph Proposition

13.2

Answer 19

for n≥2 we have X(Pn) = 2

path graph of lengh n≥2 is 2-colorable

Question 20

Chromatic Cycle Graph Proposition

13.2

Answer 20

X(Cn) = 2 when n is even
= 3 when n is odd

Question 21

Chromatic Complete Graph Proposition

13.2

Answer 21

X(Kn) = n

because any 2 vertices are adjacent

Question 22

Bipartite

13.2

Answer 22

2-colorable graphs

Question 23

Bipartite Proposition I

13.2

Answer 23

every path graph is bipartite

Question 24

Bipartite Proposition II

13.2

Answer 24

a cycle graph is bipartite iff it has an even number of vertices

Question 25

2-color Proposition I | 13.2

Answer 25

there are 2 ways to 2-color a graph one way and then swap colors | in general, for each cc there are 2 ways

Question 26

2-color Proposition II | 13.2

Answer 26

2^k ways to 2-color a garph with k cc's

Question 27

Tree Bipartite Proposition | 13.2

Answer 27

every tree is bipartite

Question 28

Bipartite Characterization Proposition | 13.3

Answer 28

a graph is bipartite iff it does not contain a cycle of odd length

Question 29

Bipartite Subgraph Proposition | 13.3

Answer 29

every subgraph of a bipartite graph is also bipartite ## Footnote subgraph can't have a cycle of odd length without OG graph having one

Question 30

Chromatic Subgraph Lemma | 13.3

Answer 30

if S is a subgraph of G, then X(S) ≤ X(G)

Question 31

Distance (notation) | 13.3

Answer 31

d(u,v)

Question 32

Distance (definition) | 13.3

Answer 32

the length of the shortest path from u to v | makes use of the well-ordering principle

Question 33

Triangle Inequality | 13.3

Answer 33

d(u,v) ≤ d(u, w) + d(w, v) | where RHS is length of walk

Question 34

Distance and 2-Coloring | 13.3

Answer 34

fix an arbitrary w0 color w R when d(w0, w) is even color w B when (w0, w) is odd

Question 35

Coloring Proposition | Self II

Answer 35

a graph has a proper coloring iff each of its cc's have a proper coloring

Question 36

Locality of Shortest Paths | Self II

Answer 36

consider the shortest path from u to v (p) let x and y be two vertices in this path ~the portion x-...-y of p is the shortest path from x to y ~d(x,y) ≤ d(u,v)

Question 37

Max Degree Colorability Proposition I | Self I

Answer 37

every graph G is Δ(G) + 1-colorable

Question 38

Δ(G) | Self I

Answer 38

the maximum degree of a node in G

Question 39

Maximum Degree of a Node in G | Self I

Answer 39

Δ(G)

Question 40

Maximum Degree Colorability Proposition II | Self I

Answer 40

there exists graphs G whose chromatic number X(G) is Δ(G) + 1

Question 41

Complete Subgraph | 13.4

Answer 41

a subgraph that is isomorphic to the complete graph Kn for some n

Question 42

Clique of/in G | 13.4

Answer 42

1) complete subgraph of G 2) a subset of the vertices of G that induces a complete subgraph

Question 43

Clique | 13.4

Answer 43

a subset of vertices where any two are adjacent

Question 44

Size of a Clique | 13.4

Answer 44

its # of vertices

Question 45

Independent Set | 13.4

Answer 45

subset of vertices S⊆V when no two vertices in S are adjacent | alt def: induced subgraph is edgeless

Question 46

Independent Set Proposition I | 13.4

Answer 46

a graph is k-colorable iff its set of vertices can be partitiioned in k independent sets ## Footnote follows directly from def of ind set, so ind sets are just another way to look at colorability

Question 47

Independent Sets Proposition II | 13.4

Answer 47

the leaves of a tree form an independent set

Question 48

Complement of a Graph | 13.4

Answer 48

G' = (V, E') where E' is the edges u-v that are not in E and u≠v | has exactly the edges that G does not have

Question 49

Complement Proposition | 13.4

Answer 49

let G = (V, E) and S⊆V S is a clique in G iff S is an independent set in G'

Question 50

How many edges does the complement of Pn have? | 13.4

Answer 50

((n-1)(n-2) / 2