11.4 Edge-Chromatic number

We prove the upper bound by induction. The theorem holds trivially for $G=K_2$. Without loss of generality assume that $G$ is connected and $G$ has strictly more than $2$ vertices. Assume that the theorem holds for any graph with fewer vertices or edges.

Let $u$ be the vertex with maximum degree i.e., $deg(u)=\mathrm{\Delta }(G)$. Let $v\sim u$ such that $deg(v)\ge 2$. If no such $v$ exists then, $G$ is a star graph and ${\chi }^{\prime }(G)=\mathrm{\Delta }(G)$ proving the theorem. Add an additional vertex $u^{\prime }$ and connect it to $u$. Call this new graph $G^{\prime }$. Observe that in $G^{\prime }$, $v$ satisfies the conditions of Lemma 11.14 with $k=\mathrm{\Delta }(G)+1$. Furthermore $G^{\prime }-v$ has fewer edges than $G$ and so ${\chi }^{\prime }(G^{\prime }-v)\le \mathrm{\Delta }(G^{\prime }-v)+1=\mathrm{\Delta }(G)+1$. Thus by Lemma 11.14, we have that $G^{\prime }$ is $(\mathrm{\Delta }(G)+1)$-edge colourable and so is $G$. ∎

We shall give a sketch of proof. For full details, see [Sudakov 2019, Chapter 8].

The proof is by induction on $k$. Let $k=1$. Then $v$ has exactly one neighbour $u$ and $(u,v)$ is an isolated edge. If $G-v$ is $1$-edge colourable, then easily we can colour the isolated edge $(u,v)$ by the same colour and get a $1$-edge colouring of $G$.

Let $k>1$. By adding additional vertices if necessary, we can assume without loss of generality that $deg(v)=k$ and there exists $w\sim v$ such that $deg(w)=k$ and $deg(u)=k-1$ for all $u\sim v,u\ne w$.

Let $c$ be a $k$-edge colouring of $G-v$. Let $X_i$ be the number of neighbours of $v$ missed by colour $i$. One neighbour misses only one colour and rest of the neighbours miss $2$ colours. So by double counting, we have that

Among all $k$-edge colourings choose one that minimizes ${\sum }_{i=1}^k{|X_i|}^2$. Suppose it holds for such a colouring that for all $i,j$

Then since ${\sum }_{i=1}^k|X_i|$ is odd, there exists $|X_i|=1$. Without loss of generality, we can assume that $|X_k|=1$. Set $X_k=\{u\}$. Let $G^{\prime }$ be the graph obtained from $G$ by deleting $(u,v)$ and all edges of colour $k$. So $G^{\prime }-v$ has a $(k-1)$-edge colouring. By induction hypothesis, we can verify that $G^{\prime }$ has a $(k-1)$-edge colouring. Now putting back the edges of colour $k$ as well as colouring $(u,v)$ with colour $k$, we get a $k$-colouring of $v$. Note that other neighbours of $v$ have other missing colours that can be used.

We are left to prove (11.1). WLOG, let $i=1,j=2$ and assume $|X_1|>|X_2|+2$. Define $H$ to be the sub-graph formed by edges of colour $1$ or $2$. Observe that $H$ consists of path or even cycle components. Since internal vertices in a path component and all vertices in a cycle component are missed by both the colours, the difference between $|X_1|$ and $|X_2|$ arises from a path component, say $P$. $P$ starts and ends with a vertex in $X_1$. Now interchanging the edge colours along $P$, we get a new colouring $c^{\prime }$ with $|X_1^{\prime }|=|X_1|-2$, $|X_2^{\prime }|=|X_2|+2$ and the rest of $X_i$’s remain unchanged. So trivially,

which contradicts the minimality of ${\sum }_{i=1}^k{|X_i|}^2$. Thus $|X_1|\le |X_2|+2$ and thus (11.1) holds. ∎