[Solved] CSDS455 Homework 18-Chordal graph

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 G₀ be the graph created by taking G and performing a sequence of edge contractions. Prove that G₀ 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 K_k minor, then any graph G⁰ with χ(G⁰) ≥k− 1 must contain a K_k−1 minor.

Problem 4: Use induction on the number of vertices of G to prove that if G does not contain a K₄ minor then G is 3-colorable.