Our Very Own Graph Theory Book: MATH 795, Fall 2020

Note that for \(|G|=0\) we have \(\chi'(G) = \Delta(G)\text{.}\) Assume that \(|G| \ge 1\) and that for all graphs with fewer edges we have \(\chi'(G) = \Delta(G)\text{.}\) Remove an edge \(xy\) from \(G\text{.}\) Color \(G-xy\) with \(\Delta(G)\) colors. Note that \(x\) and \(y\) can be adjacent to at most \(\Delta(G) - 1\) colors. That is they are each missing at least one color. Say that \(x\) is missing color \(\alpha\) and \(y\) is missing color \(\beta\text{.}\) If \(\alpha = \beta\) then we could color \(xy\) with that color and be done.

Suppose that \(\alpha \ne \beta\text{.}\) Consider a maximal walk, \(W\text{,}\) starting at \(x\) whose edges alternate colors \(\beta\) and \(\alpha\text{.}\) This walk cannot contain \(y\) becuase if it did it would end on \(y\) with an \(\alpha\) edge. This would make \(W\) odd length and \(W+xy\) on odd cycle which cannot happen (Theorem 2.0.12). Now recolor \(W\) by swapping \(\alpha\) and \(\beta\text{.}\) Since \(W\) is maximal adjecent edges of \(G-xy\) will still be colored differently. We now have an edge coloring of \(G-xy\) in which neither \(x\) nor \(y\) are adjecent to a \(\beta\)-edge. Therefore coloring \(xy\) with \(\beta\) will produce a coloring of \(G\) using \(\Delta(G)\) colors.

Let \(G=(V,E)\) be a simple undirected graph with the fewest possible edges that has no coloring. Fix a vertex \(x\in G\text{,}\) let \(y_{0}\) be a neighbor of \(x\text{,}\) and let \(c\) be a coloring of \(G-xy_{0}\text{.}\)

The degree of \(x\) and \(y_{0}\) is less than the number of colors, so there must be a color missing from each. Let \(\alpha\) denote the color missing at \(x\) and \(\beta_{0}\) be the color missing at \(y_{0}\text{.}\)

Now there must be an \(\alpha / \beta_{0}\)-path starting at \(y_{0}\) and ending at \(x\text{.}\) If not, then we would be able to swap the colors along the \(\alpha / \beta_{0}\)-path starting at \(y_{0}\) and use \(\alpha\) on \(xy_{0}\text{.}\) Now \(x\) is missing \(\alpha\text{,}\) so the last edge of the \(\alpha / beta_{0}\)-path must be colored \(\beta_{0}\text{;}\) call this edge \(xy_{1}\text{.}\)

Let \(y_{1}\) be the neighbor of \(x\) such that \(c(xy_{1})=\beta_{0}\text{,}\) and let \(\beta_{1}\) be missing for \(y_{1}\text{.}\) (We know that \(y_{1}\) is missing a color because, again, the degree of \(y_{1}\) is less than the number of colors.)

Repeating this process, we may pick \(y_{i+1}\) such that \(c(xy_{i+1})=\beta_{i}\text{,}\) with \(\beta_{i+1}\) missing for \(y_{i+1}\text{.}\) Let \(y_{k}\) be the last neighbor of \(x\) for which we can do this. Then we have a maximal sequence of vertices, \(\{ y_{0} ,y_{1} ,y_{2} ,...,y_{k-1} ,y_{k} \}\text{,}\) adjacent to \(x\text{,}\) forming a sequence of edges \(\{ xy_{0} ,xy_{1} ,xy_{2} ,...,xy_{k-1} ,xy_{k} \}\) with \(c(xy_{k})\) missing for \(y_{i-1}\text{.}\) Then we may recolor each of these edges incident to \(x\) by \(\{ c(xy_{0} )=\beta_{0} , c(xy_{1} )=\beta_{1} , c(xy_{2} )=\beta_{2} ,...,c(xy_{k-1} )=\beta_{k-1} , c(xy_{k} )=\beta_{k} \}\text{.}\)

Now \(y_{k}\) was the last vertex adjacent to \(x\) such that we could define an \(\alpha / \beta\)-path using our recursive pattern, so there must exist a \(y_{i}\text{,}\) \(1\leq i\leq k-1\) such that the \(\alpha / \beta_{k}\)-path ends at \(y_{i}\text{.}\) Let \(xy_{i}\) be the last edge of this \(\alpha / \beta_{k}\)-path.

But then we have that \(\beta_{k}=\beta_{i-1}\) by our construction. Then there exists an \(\alpha / \beta_{i-1}\)-path from \(y_{i-1}\) to \(x\) through \(y_{i}\text{.}\) But there is only one \(\alpha / \beta_{k}\) path coming off of \(y_{i}\text{,}\) and by our assumption it is going to two different vertices adjacent to \(x\text{,}\) \(y_{k}\) and \(y_{i-1}\text{,}\) a contradiction.