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

A proper $k$-coloring assigns one of $k$ colors to each vertex so adjacent vertices receive different colors. The chromatic number $\chi (G)$ is the least such $k$. Order the vertices arbitrarily and color greedily. At most $\Delta (G)$ colors are forbidden by previously colored neighbors, soEquality occurs for every possible maximum degree: use $K_1$ for $\Delta =0$, $K_2$ for $\Delta =1$, an odd cycle for $\Delta =2$, and $K_{\Delta +1}$ for every $\Delta \ge 3$.

A graph is $k$-connected when it has more than $k$ vertices and remains connected after deletion of fewer than $k$ vertices. In a noncomplete 3-connected graph, choose a vertex $v$ with two nonadjacent neighbors $a,b$. Since $G-\{a,b\}$ is connected, take a spanning tree rooted at $v$ and order its vertices so every vertex other than $v$ has a later tree neighbor. Color $a$ and $b$ first with the same color, then greedily color the other vertices in reverse tree order, leaving $v$ last. Every nonfinal vertex has one uncolored neighbor and therefore sees at most $\Delta -1$ colors. At $v$, the two neighbors $a,b$ share a color, so again at most $\Delta -1$ colors occur. HenceThis is the relevant 3-connected case of Brooks' theorem.

Euler's formula for a connected plane graph is $|V|-|E|+|F|=2$. If the graph is triangle-free, every face has boundary length at least four, soEuler's formula then gives $|E|\le 2|V|-4$, so the average degree is less than four. There is a vertex of degree at most three. Delete it, color the remaining graph inductively with four colors, and restore it using a color absent from its at most three neighbors. Thus

The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colors in a proper coloring of edges, where incident edges receive distinct colors. Hall marriage theorem says a bipartite graph has a matching saturating one side exactly when $|N(S)|\ge |S|$ for every subset $S$ of that side.

In a 4-regular bipartite graph, the $4|S|$ edges leaving $S$ all enter $N(S)$, whose vertices can receive at most $4|N(S)|$ such edges. Hence Hall's condition holds and there is a perfect matching. Remove it and repeat in the resulting 3-, 2-, and 1-regular bipartite graphs. The four perfect matchings give a four-edge-coloring, while every vertex requires four distinct colors. Therefore