91Ó°ÊÓ

Prove that the chromatic number of a disconnected graph is the largest of the chromatic numbers of its connected components.

Prove that the chromatic polynomial of a disconnected graph equals the product of the chromatic polynomials of its connected components.

Prove that a graph with chromatic number equal to \(k\) has at least \(\left(\begin{array}{c}k \\ 2\end{array}\right)\) edges.

Prove that the chromatic polynomial of a cycle graph \(C_{n}\) equals $$ (k-1)^{n}+(-1)^{n}(k-1) $$

Prove that the chromatic number of a graph that has exactly one cycle of odd length is 3 .

Use the algorithm for computing the chromatic polynomial of a graph to da termine the chromatic polynomial of the graph \(Q_{3}\) of vertices and edges of in three-dimensional cube.

Let \(G\) be a planar graph of order \(n\) in which every vertex has the same degree k. Prove that \(k \leq 5\).

Let \(G\) be a planar graph of order \(n \geq 2\). Prove that \(G\) has at least two vertices whose degrees are at most \(5 .\)

A graph is called color-critical provided each subgraph obtained by removing a vertex has a smaller chromatic number. Let \(G=(V, E)\) be a color-critical graph. Prove the following: (a) \(\chi\left(G_{V-\\{x\\}}\right)=\chi(G)-1\) for every vertex \(x\). (b) \(G\) is connected. (c) Each vertex of \(G\) has degree at least equal to \(\chi(G)-1\). (d) \(G\) does not have an articulation set \(U\) such that \(G_{U}\) is a complete graph. (e) Every graph \(H\) has an induced subgraph \(G\) such that \(\chi(G)=\chi(H)\) and \(G\) is color-critical.

Prove that the complement of a disconnected graph is connected.