# If graph G is bipartite with largest vertex degree $\Delta$(G) , then $\chi'(G)$ = $\Delta$(G)

$\mathbf{\chi'(G)}$ represents edge-chromatic index

Proof by induction on the number of edges:

Base case: if $\mathbf{|E(G)| = 1}$ then $\mathbf{\Delta(G) = 1}$ and $\mathbf{\mathbf{\chi'(G)} = 1}$ (Thus $\mathbf{\chi'(G)}$ = $\Delta$(G))

Assume: Every bipartite graph $\mathbf{G}$ with $\mathbf{|E(G)| = k}$ has $\mathbf{\chi'(G) = \Delta(G)}$

Let $\mathbf{G}$ be bipartite with $\mathbf{|E(G)| = k+1}$

Let $\mathbf{uv \in E(G)}$ . Then $\mathbf{G-uv}$ is a bipartite graph with $\mathbf{k}$ edges and thus by induction $\mathbf{\chi'(G-uv) = \Delta(G-uv) \leq \Delta(G)}$

In graph $\mathbf{G-uv}$ , $\mathbf{Deg(u)}$ and $\mathbf{Deg(v)\leq \Delta(G)-1}$

From here I am not sure how to continue, I was thinking of continuing by dividing in to 2 cases, CASE#1 If degree of $\mathbf{u}$ and $\mathbf{v < \Delta(G)-1}$ then add an edge and paint it one of the colors of $\mathbf{\Delta(G)}$ which is not adjacent to either vertex $\mathbf{u}$ or $\mathbf{v}$. CASE#2 would be if at least one of the vertex from $\mathbf{u}$ and $\mathbf{v}$ has degree $\mathbf{\Delta(G)-1}$ then add an edge and paint it with a color present in $\mathbf{\Delta(G)}$ edges and not in $\mathbf{\Delta(G)-1}$ edges.

• I don’t see how can we realize induction step if we have already used all $\Delta(G)$ colors to color the edges incident to $u$ or $v$. – Alex Ravsky Sep 9 '17 at 18:16

If $$\mathcal{C} = \left(E_1, E_2 , \cdots , E_k\right)$$ is an optimal $$k$$-edge colouring of $$G$$ and there is a vertex $$u$$ in $$G$$ and colours $$i$$ and $$j$$ such that $$i$$ is not represented at $$u$$ and $$j$$ is represented at least twice at $$u$$, then the component of $$G\left[E_i\cup E_j\right]$$ that contains $$u$$ is an odd cycle.