# How can we create a graph $G'$ by subdividing the edge $e$ with a new degree two vertex $z$?

Let $G=(V,E)$ be a bipartite graph and e=uv an edge where $\text{deg}(u)<\Delta$. How can we create a graph G' by subdividing the edge e with a new degree two vertex z.

i.e: we delete $e$ and add a new vertex $z$ which is adjacent to $u$ and $v$.

Show that $X^E(G')=\Delta$.

$X^E(G')$ : the edge chromatic number of $G'$

-
The title doesn't really seem to match what the question apparently is (i.e. 'Show that $X^E(G') = \Delta$'). – Tara B Feb 12 '13 at 19:27

I assume it is known that for the bipartite graph $G$, $X^E(G)=\Delta$. Consider an according edge colouring. Let $\alpha$ be the colour of $uv$. Since $\operatorname{deg}(u)<\Delta$, there is at least one color $\beta$ not occuring for an edge incident with $u$. Assign $\alpha$ to $zv$ and $\beta$ to $uz$.
EDIT: It appears, we don't need that $G$ is bipartite. It is sufficient that $G$ is a class 1 graph and $\operatorname{deg}(u)<\Delta$.
Technically, this only shows $X^E(G)\leq \Delta$. – Tara B Feb 12 '13 at 19:28
Yes, but it is know (and essentially trivially true that) $X^E(G)\geq \Delta$ for all graphs $G$, @TaraB. – Thomas Andrews Feb 12 '13 at 19:29
I was more or less being silly, but what is $\Delta$, actually? – Tara B Feb 12 '13 at 19:30
@TaraB I assume $\Delta=\max\{\operatorname{deg}(v)\mid v\in V\}$. – Hagen von Eitzen Feb 12 '13 at 19:31