Show that if deg(V0)=3, then we may Δ+1 edge colour such a graph G

[khanak]

Suppose that every odd cycle in a graph [FONT=MathJax_Math]G contains some specific vertex [FONT=MathJax_Math]V[/FONT][FONT=MathJax_Main]0[/FONT][/FONT]


Show that if [FONT=MathJax_Main]deg[FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]V[/FONT][FONT=MathJax_Main]0[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]3[/FONT], then we may [FONT=MathJax_Main]Δ[/FONT][FONT=MathJax_Main]+[/FONT][FONT=MathJax_Main]1[/FONT] edge colour such a graph [FONT=MathJax_Math]G[/FONT].


So far i know that

If we remove two of the edges [FONT=MathJax_Math]V[/FONT][FONT=MathJax_Main]0[/FONT][FONT=MathJax_Math]A[/FONT], [FONT=MathJax_Math]V[/FONT][FONT=MathJax_Main]0[/FONT][FONT=MathJax_Math]B[/FONT] incident with [FONT=MathJax_Math]V[/FONT][FONT=MathJax_Main]0[/FONT], the graph becomes bipartite (because there are no odd cycles). A bipartite graph has [FONT=MathJax_Math]χ[/FONT][FONT=MathJax_Math]E[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]G[/FONT][FONT=MathJax_Main]′[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]=[/FONT][FONT=MathJax_Main]Δ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]G[/FONT][FONT=MathJax_Main]′[/FONT][FONT=MathJax_Main])[/FONT][FONT=MathJax_Main]≤[/FONT][FONT=MathJax_Main]Δ[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Math]G[/FONT][FONT=MathJax_Main])[/FONT]. I am just not understanding how to construct a valid colouring for [FONT=MathJax_Math]G[/FONT] from this[/FONT]

 

[daon2]

I have never taken a class in graph theory, but humor me. If a graph contains two vertices as below

-(v)--(w)
|_|

Then every odd cycle contains v, but it is not 4-colorable (delta(G)=3).