Next week we will be discussing minors. Please skim through your text’s sections on minors and topological minors.
Problem 1: Let G be a chordal graph. Let G0 be the graph created by taking G and performing a sequence of edge contractions. Prove that G0 is also chordal.
Problem 2: Let G be a planar graph. Prove that any minor of a planar graph must also be planar. (Don’t use Kuratowski’s Theorem.)
Problem 3: Prove that if any graph G with χ(G) ≥ k contains a Kk minor, then any graph G0 with χ(G0) ≥k− 1 must contain a Kk−1 minor.
Problem 4: Use induction on the number of vertices of G to prove that if G does not contain a K4 minor then G is 3-colorable.
