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

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

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