Mugger Theorems, Sketches, and Proofs

Question 1

What is the Havel Hakimi Theorem?

Answer 1

A nonincreasing sequence of nonnegative integers S: d1, … , dp, for (p ≥ 2) is graphical if and only if, the sequence S1: d_{2}-1, …, d_{d1+1}-1, d_{d1+2}, …, d_p is graphical.

Question 2

What is Hall’s Theorem?

Answer 2

An bipartite graph G with parts X and Y has a matching that saturates X if and only if |N(S)|≥|S| for all S subsets of X.

Question 3

What is the Konig-Egerváry Theorem?

Answer 3

If G is a bipartite graph, then the maximum size of a matching in G equals the minimum size of a vertex cover of G.

Question 4

What is Tutte’s Theorem?

Answer 4

A graph G has a 1-factor if and only if o(G-S) ≤ |S| for every S subset of the V(G).

Question 5

What is Menger’s Theorem?

Answer 5

Let u and v be nonadjacent vertices in a graph G. The minimum number of vertices needed to separate u and v is equal to the maximum number of internally disjoint u,v-paths in G.

Question 6

What is Brook’s Theorem?

Answer 6

If G is a graph with maximum degree ∆ , then Chi(G) ≤ ∆(G,) unless G is a complete graph or odd cycle.

Question 7

What is Euler’s Theorem?

Answer 7

Let G be a connected plane graph with n vertices, e edges, and f faces. Then n - e + f = 2.

Question 8

What is Kuratowski’s theorem?

Answer 8

A graph G is planar if and only if G contains no subdivision of K_5 or K_{3,3}.

Question 9

What is a sketch of Tutte’s Theorem?

Answer 9

1. Let G be a 1-factor, let S be a subset of V(G). Since it’s a 1-factor, at least one vertex in each component of G-S has a neighbor in S. In fact, there’s a distinct vertex in S, so o(G-S) ≤ |S| for all S subsets of V(G).
2. Now prove the converse. Let G be a graph such that o(G-S) ≤ |S| for all S subsets of V(G).
   2a. Add edges to G
   
   • notice o(G’-S) ≤ o(G-S) ≤ |S|.
     2b. Assume G’ is a graph that satisfies o(G’-S) ≤ |S| but adding any edge will create a 1-factor.
     Let T be the set of vertices that are adjacent to every other vertex.
     2c. Case 1: G’-T is the disjoint union of complete graphs
   • every odd component has one awkward vertex. Add the edges from these to the vertices in T. Leftovers in T can be adjacent to each other. Walah! Perfect matching, 1-factor.
     2d. Case 2: G’-T has a component that is not complete
   • Here we find the symmetric difference of two maximum matchings conditioning on two endpoints of a p3 and a vertex not in T, y, and a vertex y isn’t adjacent to, w.
   • Our symmetric difference proves G’ has a 1-factor. Contradiction!
     QED.

Question 10

What is a sketch of Brook’s Theorem?

Answer 10

Consider 3 cases:
Case 1: G is not regular. Chose a vertex v that has minimum degree. Use a Depth First Search to find the spanning tree. Prune leaves of the DFS tree to order the vertices, have v be last. This order results in Chi(G) ≤ ∆(G).
Case 2: G is regular with a cut vertex v. We have components G1 and G2, (both include v). ∆(G1) = ∆(G2) = ∆(G). Thus G1 and G2 can be colored properly with ∆(G) colors, and Chi(G) ≤ ∆(G).
Case 3: G is regular and two connected.
a) Then G is a cycle, complete graph, or a complete bipartite. The complete graph doesn’t matter, and both the cycle and complete bipartite can be colored with 2 colors, and 2 ≤ ∆(G).
b) So G is regular, 2-connected, and has a DFS tree that is not a path. v is where our P branches, x and y are the first vertices after v. Do a DFS of (G-{x,y}), order the vertices accordingly, and let x and y be first. x and y will have the same color, and so v will be colored with the ∆(G)th color. Thus Chi(G) ≤ ∆(G).

Question 11

What is the proof of Euler’s Theorem?

Answer 11

Proof by induction on n. Base case n=1. Each extra loop divides a face into two. So e += 1 and f += 1, they cancel out, and n-e+f=2 holds.
For n ≥ 2, consider the edge w. Consider G•w = G’. G’ has n -=1, BUT has f += 1! G’, by induction has n’ - e’ +f’ = 2. G has (n+1) - (e) + (f-1) = 2, which gives n-e+f-1+1 = 2, or
n-e+f=2!