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.
