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

  • $\begingroup$ 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$. $\endgroup$ – Alex Ravsky Sep 9 '17 at 18:16

Hint: Prove the contrapositive by using the following fact:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.