Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For the graph $D_n$ created from complete graph $K_n$ by replacing one of edges by path on 3 vertices.

For example, the graph attached is $D_4$. enter image description here

I can prove that the edge chromatic number is $n$. Now I do not know how to prove that if we delete any edge in $D_n$, then it is $n-1$ edge colorable.

share|cite|improve this question
Didn't you remove 2 edges in $D_4$? – Franck Dernoncourt Jan 24 '14 at 23:09
Another way to put it: $D_n$ is obtained from $K_n$ by adding a (degree two) vertex in the middle of one of the edges. – Hagen von Eitzen Jan 24 '14 at 23:11
Yes, Hagen's explanation is what I really mean. – Ginger Jan 24 '14 at 23:27

Seems I proved it by myself.

\begin{thm} \label{thm:edge_color_Kn} If $n$ is odd, then the chromatic index of complete graph $K_n$ is $n$; If $n$ is even, the chromatic index of $K_n$ is $n-1$. \end{thm}

\begin{lemma} If we remove any edge in $D_d$, then the remaining graph is $d$-edge-colourable. \end{lemma}

\begin{proof} If we denote the vertices on $D_d$ by $1,2,\dots, d,d+1$ where vertices 1 and $d$ has degree $d-1$ and vertex $d+1$ has degree 2. Because of the symmetry, the edge being removed has 3 cases: 1. it is $(1,d+1)$ or $(d,d+1)$; 2. it is $(1,i)$ or $(d,i)$ where $i\in{2,\dots, d-1}$; 3. It is $(i,j)$ where $i,j\in{2,\dots, d-1}$.

From theorem~\label{thm:edge_color_Kn} we know that there is a $d$ edge coloring of $K_d$. And in $D_d$ we remove from $K_d$ the edge $(1,d)$ and add two edges $(1,d+1)$ and $(d,d+1)$. For the case 1, w.l.o.g. we assume that $(1,d+1)$ is removed, then we just color $(d,d+1)$ with the same color of $(1,d)$ in the edge coloring of $K_d$. It is a $n$ proper edge coloring of the remaining graph. For the case 2, w.l.o.g., we assume that $(1,2)$ is removed, then we color $(1,d+1)$ with the color of $(1,2)$ in $K_d$ and color $(d,d+1)$ with the color of $(1,d)$ in $K_d$, this constructs a proper edge coloring of the remaining graph. For the case 3, w.l.o.g., we assume we remove the edge $(2,3)$. Then we color $(d,d+1)$ with the color of $(1,d)$ in $K_d$. And the degree of vertex 1 in $K_d$ is $d-1$, so there is one color of $d$ which does not color any edge attaches to vertex 1, we use this color to color $(1,d)$. This is a proper edge coloring. \end{proof}

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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