Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 3 / 17F (Graph Theory)

The Brooks' theorem states that a finite connected simple graph with maximum vertex degree $\Delta$ has chromatic number at most $\Delta$, unless it is a complete graph or an odd cycle graph; those exceptions have chromatic number $\Delta +1$.

First, if the graph is not regular, choose a vertex $v$ of degree less than $\Delta$ and a spanning tree rooted at $v$. Order vertices with every child before its parent, and apply the greedy coloring algorithm. Every vertex except $v$ has an as-yet uncolored parent, so has at most $\Delta -1$ colored neighbors; $v$ also has fewer than $\Delta$ neighbors. Thus $\Delta$ colors suffice. This justifies reducing to the regular case.

Now let $G$ be regular, 3-connected and not complete. A shortest path between two nonadjacent vertices contains an induced two-edge path $a,v,b$ with $a,b$ nonadjacent. By 3-connectivity, $G-\{a,b\}$ is connected. Color $a,b$ with the same color. Choose a spanning tree of the remaining graph rooted at $v$ and color its vertices in child-before-parent order. Each vertex other than $v$ again has an uncolored parent and thus at most $\Delta -1$ already colored neighbors. At the last vertex $v$, the two neighbors $a,b$ share a color, so its $\Delta$ neighbors use at most $\Delta -1$ distinct colors. A color is therefore available at every step, proving $\boxed{\chi (G)\le \Delta }$ in the required 3-connected noncomplete case. A 3-connected graph has $\Delta \ge 3$, so the odd-cycle exception cannot arise here.

The Vizing theorem states that for every finite simple graph of maximum vertex degree $\Delta$, its edge chromatic number satisfies $\boxed{\Delta \le {\chi }^{\prime }(G)\le \Delta +1}$. The lower bound follows because all edges incident to a maximum-degree vertex need different colors. The simplicity hypothesis matters: unrestricted multigraphs need not satisfy this upper bound.

The first assertion is false. The complete graph $K_4$ has $\chi (K_4)=4$, but ${\chi }^{\prime }(K_4)=3$: color each of its three perfect matchings with its own color. It is connected and has more than two vertices.

The second assertion is false. Take the crown graph with bipartition $a_1,\dots ,a_5$ and $b_1,\dots ,b_5$, joining $a_i$ to $b_j$ exactly when $i\ne j$. Its chromatic number is two. In the ordering $a_1,b_1,a_2,b_2,\dots ,a_5,b_5$, the greedy coloring algorithm assigns color $i$ to both $a_i,b_i$: both see all previously used colors, but they are not adjacent to each other. It therefore uses five colors, exceeding $2\chi (G)=4$. Taking more pairs makes the ratio arbitrarily large.

The third assertion is true. When an edge is colored greedily, at most $2\Delta -2$ adjacent edges have previously received colors. Thus the greedy coloring algorithm uses at most $2\Delta -1\le 2{\chi }^{\prime }(G)-1<2{\chi }^{\prime }(G)$ colors whenever the graph has an edge. The edgeless case is trivial. This bound holds for every edge ordering.