# Thread: Graph Theory- Edge Colouring

1. ## Graph Theory- Edge Colouring

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

2. well graphs are either class 1 or class 2, so all you have to show is that $\chi'(G) \neq \Delta(G)$