Let $G$ be a simple graph whose vertices of maximum degree $\Delta $ induce a
forest. Show that $\chi ^{'}=\Delta$.
I actually don't understand this question well,is it saying that if we take induced sub graph on the vertices with degree $\Delta$ will be a forest?now with this hypothesis show that $\chi ^{'}=\Delta$.
if it is like it that I explained we take every tree of this forest,this arbitrary tree should have some vertices of $\Delta$ degree on other vertices should be leaves,so it is obvious that we can color the edges with $\Delta$ colors.
but I think my understanding is wrong (maybe)!
so it will be great that if you help me with this ,thanks.
Best Answer
Lemma 17.3 states that if $G$ is a simple graph, $v$ is a vertex of $G$, $e$ is an edge of $G$ incident to $v$, $k \geq \Delta$ is an integer, and $G \setminus e$ has a $k$-edge-colouring with respect to which every neighbour of $v$ in $G$ has at least one available colour then $G$ is $k$-edge-colourable.
(I expect that those used to proving Vizing's Theorem without this intermediate lemma can adapt the proof in a similar way, but it would make the question rather more difficult.)
We induct on the number of edges.
Take a vertex $v$ that is a leaf in the induced forest (the forest must contain at least one vertex because $G$ has at least one vertex of maximal degree).
If $v$ is adjacent to some other vertex $w$ in the induced forest, let $e=vw$. (Note that there can only be one such $w$ as $v$ is a leaf.) Otherwise let $e$ be any edge incident to $v$.
By the inductive hypothesis, $G \setminus e$ has a $\Delta$-edge-colouring.
Thanks to our choice of $v$ and $e$, no vertex of $G$ that is adjacent to $v$ (in $G$) has degree greater than $\Delta-1$ in $G \setminus e$.
This means that each neighbour of $v$ in $G$ must have at least one available colour in the $\Delta$-edge-colouring of $G \setminus e$, so by lemma 17.3 we have that $G$ is $\Delta$-edge-colourable as required.