# edge coloring of a specific graph

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

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.

-
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

\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}