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

1.5k Views Asked by At

$\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.