Prove Vizing Class 1 if maximum degree vertices induce forest by induction

147 Views Asked by At

I tried to prove that if for a simple graph $G$, vertices of maximum degree induce a forest, then $\chi'(G) \leq \Delta(G)$, in other words, the graph is in Vizing Class 1.

When I applied induction on $|E(G)|$, I encountered the problem, that if there is only one vertex $v \in V(G)$ having maximum degree, I cannot ensure that I can apply the induction hypothesis on $G\setminus e$ for an edge $e$ incident with $v$.

If I remove $e$, there might be vertices of degree $\Delta(G) - 1$ inducing a cycle. This graph is an example. If we remove the degree 5 vertex, then the degree 4 vertices don't induce a forest.

How can I solve this problem? Is there a way to fix this proof?

1

There are 1 best solutions below

0
On

if the maximum degree of G\e is not Δ(G),then Δ(G\e)+1≤Δ(G) and by Vizing there is a Δ(G) edge coloring. Thats all you need