Past exam of the graph theory course of the University of Oxford / 2023 / 1

A proper edge colouring assigns colours to the edges of a graph so that distinct edges sharing a vertex have different colours. The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colours in such an assignment. Equivalently, it is the least number of matchings in a graph whose disjoint union is the entire collection of edges.

Vizing's theorem states that a finite simple graph of maximum degree $\Delta$ satisfiesThe lower bound holds because all edges incident with a vertex of vertex degree $\Delta$ require different colours.

Hall's marriage theorem states that a finite bipartite graph with vertex sets $A,B$ has a matching in a graph saturating $A$ if and only ifwhere $N(S)\subseteq B$ is the graph neighbourhood of $S$. Here matching saturation means that each vertex of $A$ is incident with an edge of the matching in a graph; it does not require every vertex of $B$ to be met.

Let $A_{\Delta }=\{a\in A:d_G(a)=\Delta \}$. Apply Hall's marriage theorem to the induced subgraph on $A_{\Delta }\cup B$, which is a bipartite graph. For any subset $S\subseteq A_{\Delta }$, double counting the edges from $S$ to its graph neighbourhood givesThe equality uses the fact that every neighbour of $S$ lies in $B$, so all edges incident with $S$ have been counted. The final inequality uses the maximum degree bound on $B$. Since $\Delta >0$, division gives the Hall condition $|S|\le |N(S)|$.

Consequently there is a matching in a graph $M_1$ saturating $A_{\Delta }$. If $A_{\Delta }$ is empty, use the empty matching in a graph. This proves the required matching covering maximum-degree vertices in a bipartite graph on the specified side; other vertices need not be met.

By part (i), choose a matching in a graph $M_1$ meeting all vertices of vertex degree $\Delta$ in $A$. Interchanging the two vertex sets gives a matching in a graph $M_2$ meeting all such vertices in $B$. Consider the spanning subgraph $H$ with edges $M_1\cup M_2$.

Every vertex has vertex degree at most two in $H$. An edge belonging to both matchings in a graph forms a whole two-vertex connected component of a graph, since neither endpoint can meet another edge of either matching in a graph. On every other nontrivial connected component of a graph, the edges alternate between $M_1$ and $M_2$, so the connected component of a graph is a graph path or an even graph cycle. We select one of the two matchings in a graph separately on each connected component of a graph.

On a graph cycle, either choice covers every vertex. On a graph path with an odd number of edges, the first and last edges belong to the same matching in a graph; choose it, and it covers every vertex of the graph path. For a common edge, choose that edge.

It remains to treat a graph path with a positive even number of edges. Its endpoints lie in the same side of the bipartite graph. Every internal vertex meets both matchings in a graph. If both endpoints lie in $A$, choose $M_1$: every endpoint of vertex degree $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all vertices of vertex degree $\Delta$ in that connected component of a graph.

Finally, an isolated vertex of $H$ cannot have vertex degree $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected edges over the connected components of a graph is a matching in a graph, because different connected components of a graph have disjoint vertex sets. It meets every vertex of vertex degree $\Delta$ in $G$. The useful mechanism is the union of two matchings and its alternating connected components of a graph.

Use mathematical induction on the maximum degree $\Delta$, including $\Delta =0$ as the base case. A graph of maximum degree zero has no edges, so zero colours suffice.

For $\Delta >0$, part (ii) supplies a matching in a graph $M$ meeting every vertex of vertex degree $\Delta$. Delete its edges, retaining all vertices. Each vertex formerly of maximum degree loses one incident edge; every other vertex already had vertex degree at most $\Delta -1$. HenceThe resulting graph is still a bipartite graph. By mathematical induction, it has a proper edge colouring using at most $\Delta -1$ colours. Give every edge of $M$ one new colour. Since $M$ is a matching in a graph, this produces a proper edge colouring of $G$ with at most $\Delta$ colours. The edges at a vertex of maximum degree require at least $\Delta$ colours, soThis is Kőnig's line colouring theorem.

For even $r\ge 2$, take the complete graph $K_{r+1}$. It is an $r$-regular graph on an odd number of vertices. Every matching in a graph has at most $r/2$ edges, so $r$ colours in a proper edge colouring could cover at most $r^2/2$ edges. ButTherefore ${\chi }^{\prime }(K_{r+1})>r$; Vizing's theorem gives ${\chi }^{\prime }(K_{r+1})=r+1$. This includes the graph triangle when $r=2$.

For odd $r\ge 3$, first construct a graph $H_r$ on $r+2$ vertices. Start with the complete graph onand delete the edges $va$, $vb$, and $c_1{c}_2,c_3{c}_4,\dots ,c_{r-2}{c}_{r-1}$. The pairing is possible because $r-1$ is even. In the initial complete graph, every vertex has vertex degree $r+1$. The distinguished vertex $v$ loses two edges and every other vertex loses exactly one, givingTake two disjoint copies of $H_r$, with distinguished vertices $v,v^{\prime }$, and add the edge $v{v}^{\prime }$. The resulting simple graph $G_r$ is an $r$-regular graph. The added edge is the only edge between the two copies; each copy has the odd number $r+2$ of vertices.

Suppose an $r$-colour proper edge colouring existed. At each vertex, the $r$ incident edges would use all $r$ colours. Thus each colour would form a perfect matching. Any perfect matching must use $v{v}^{\prime }$: without it, each odd-sized copy would have to be covered by internal pairs, which is impossible by parity. Therefore all $r$ colour classes would have to contain the same edge $v{v}^{\prime }$, a contradiction. Hence Vizing's theorem again givesThese constructions give class two regular graphs for every $r\ge 2$. The odd-$r$ construction exhibits the bridge obstruction to regular edge colouring; $H_r$ is a connected graph because every vertex other than $a,b,v$ is adjacent to $v$, while $a,b$ are adjacent to those vertices.