Module 13 Vocab Flashcards
Spanning Subgraph
13.1
a subgraph whose vertex set is the entire set V
(of the original graph G)
Spanning Tree
13.1
of a connected graph G,
a spanning subgraph that’s also a tree
Spanning Forest
13.1
a spanning tree for each of hte cc’s of G
Spanning Tree Proposition
13.1
every connected graph has a spanning tree
hence every graph has a spanning forest
Cut Edge
13.1
erasing it strictly increases the number of cc’s
Cut Edge Proposition
13.1
removing a cut edge in a graph increases the number of cc’s by exactly one
Edge Proposition II
13.1
an edge is a cut edge iff it does not belong to any cycle
every edge in a cycle is not a cut edge
Edge Corollary
13.1
a connected graph is a tree iff each one of its edges is a cut edge
Edge-Prunning Algorithm
13.1
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
Edge-Growing Algorithm
13.1
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
k-coloring
13.2
a function
f: V→[1..k]
each vertex maps to a color
Proper Coloring
13.2
when for any edge u-v we have f(u) ≠ f(v)
adjacent vertices are different colors
k-colorable
13.2
a graph that admits a proper k-coloring
what does k-colorable imply?
13.2
j-colorable for any j ≥ k
n-colorable
13.2
a graph with n vertices is n-colorable
Chromatic Number (notation)
13.2
X(G)
“chi of G”
Chromatic Number (definition)
13.2
the smallest k such that G is k-colorable
Chromatic Proposition
13.2
X(G) = 1 iff G is edgeless
Chromatic Path Graph Proposition
13.2
for n≥2 we have X(Pn) = 2
path graph of lengh n≥2 is 2-colorable
Chromatic Cycle Graph Proposition
13.2
X(Cn) = 2 when n is even
= 3 when n is odd
Chromatic Complete Graph Proposition
13.2
X(Kn) = n
because any 2 vertices are adjacent
Bipartite
13.2
2-colorable graphs
Bipartite Proposition I
13.2
every path graph is bipartite
Bipartite Proposition II
13.2
a cycle graph is bipartite iff it has an even number of vertices
2-color Proposition I
13.2
there are 2 ways to 2-color a graph
one way and then swap colors
in general, for each cc there are 2 ways
2-color Proposition II
13.2
2^k ways to 2-color a garph with k cc’s
Tree Bipartite Proposition
13.2
every tree is bipartite
Bipartite Characterization Proposition
13.3
a graph is bipartite iff it does not contain a cycle of odd length
Bipartite Subgraph Proposition
13.3
every subgraph of a bipartite graph is also bipartite
subgraph can’t have a cycle of odd length without OG graph having one
Chromatic Subgraph Lemma
13.3
if S is a subgraph of G, then
X(S) ≤ X(G)
Distance (notation)
13.3
d(u,v)
Distance (definition)
13.3
the length of the shortest path from u to v
makes use of the well-ordering principle
Triangle Inequality
13.3
d(u,v) ≤ d(u, w) + d(w, v)
where RHS is length of walk
Distance and 2-Coloring
13.3
fix an arbitrary w0
color w R when d(w0, w) is even
color w B when (w0, w) is odd
Coloring Proposition
Self II
a graph has a proper coloring iff each of its cc’s have a proper coloring
Locality of Shortest Paths
Self II
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)
Max Degree Colorability Proposition I
Self I
every graph G is Δ(G) + 1-colorable
Δ(G)
Self I
the maximum degree of a node in G
Maximum Degree of a Node in G
Self I
Δ(G)
Maximum Degree Colorability Proposition II
Self I
there exists graphs G whose chromatic number X(G) is Δ(G) + 1
Complete Subgraph
13.4
a subgraph that is isomorphic to the complete graph Kn for some n
Clique of/in G
13.4
1) complete subgraph of G
2) a subset of the vertices of G that induces a complete subgraph
Clique
13.4
a subset of vertices
where any two are adjacent
Size of a Clique
13.4
its # of vertices
Independent Set
13.4
subset of vertices S⊆V
when no two vertices in S are adjacent
alt def: induced subgraph is edgeless
Independent Set Proposition I
13.4
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
Independent Sets Proposition II
13.4
the leaves of a tree form an independent set
Complement of a Graph
13.4
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
Complement Proposition
13.4
let G = (V, E) and S⊆V
S is a clique in G iff S is an independent set in G’
How many edges does the complement of Pn have?
13.4
((n-1)(n-2) / 2
