Let G = (V, E) be a loop-free undirected graph. We call G color-critical if x(G) > x(G - v) for all v ∈ V.
(a) Explain why cycles with an odd number of vertices are color-critical while cycles with an even number of vertices are not color-critical.
(b) For n ∈ Z+, n > 2, which of the complete graph Kn are color-critical?
(c) Prove that a color-critical graph must be connected.
(d) Prove that if G is color-critical with x (G) = k, then deg(v) ≥ k - 1 for all v ∈ V.