[Solved] CSDS455 Homework 18-Chordal graph

Next week we will be discussing minors. Please skim through your texts 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. (Dont use Kuratowskis 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_k1 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.