CSDS 455: Applied Graph Theory

Homework 18

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.