Let G be a simple graph with n vertices and m edges.
Show that if n is odd and m > ((n-1)*Δ(G))/2 , then χ′(G) = Δ(G)+1
I'm having trouble with this problem, I know Vizing theorem and it states that in order for χ′(G) = Δ(G)+1 to be true G must be class 2.
How do I show G is class 2? Class 2 Graph -- from Wolfram MathWorld
Δ(G) is the maximum degree of G.
Or is there an easier way.
Thanks and plus rep!
EDIT: It's not enough to show that if it would hold for one example under the criteria it would hold for all is it? I don't think so