# Proving Vizing's Theorem using Induction

So I would like to prove Vizing's theorem (let d be the maximum degree of any vertex in graph G, any graph can be edge-colored with d or d+1 colors) using induction on the edges of G...here's my start...E=edges, d=max degree

My problem comes in SUBCASE 2 in both CASE 1 and CASE 2, it is the same problem...

(i) E=1, d=1, only one color is needed to color one edge, base case satisfied.

(ii) Induction Hypothesis: A graph G with E=n can be colored with d or d+1 colors, show that a graph H with E=n+1 can be colored using d or d+1 colors.

CASE 1: The new edge is drawn in graph G to a vertex with degree d...

SUBCASE 1: Graph G has d colors. Since there are d colors, any vertex of degree d must have EVERY color edge drawn to it. Adding a new edge to it must require a new color, and it can be drawn to any other vertex since it is a new color, thus there are d+1 colors in the graph H with E=n+1 edges and the maximum degree of any vertex in H is now d+1.

SUBCASE 2: Graph G has d+1 colors. Since there are d+1 colors, no vertex can have every color since the max degree is d. Any vertex of degree d is missing a color, and thus every vertex must be missing a color. Draw the new edge with the missing color to one of the other vertices missing that color (first problem, how can I prove that there must be two vertices missing that color, the one of degree d and the one I am drawing it to? Do I need to draw it to an existing vertex, or can I create a new vertex?). Thus, you have graph H with E=n+1 edges that is colored with d+1 colors and a new maximum degree in H of d+1.

CASE 2: The new edge is not drawn in graph G from a vertex with degree d.

SUBCASE 1: Graph G has d colors. Choose vertex A such that its degree is d' < d, then draw a new edge from vertex A to any vertex B whose degree d" < d in G, if the vertex B has that color, use a new color not in d, or if the vertex B does not have the color, no new color is needed. Either there are d+1 colors in the new graph H with E=n+1 edges or there are d colors in the graph H with E=n+1 edges.

SUBCASE 2: Graph G has d+1 colors. No vertex can have every color since there are d+1 colors and the maximum degree is d. Choose vertex A such that its degree is d' < d. This vertex must be missing at least two colors, choose one and draw an edge of that color to any other vertex B whose degree d" < d in G that is missing that color as well (again, same problem, how do I prove that there is a second degree missing that color, or do I even need a second degree and can I draw it to a new vertex?). Thus, you have graph H with E=n+1 edges and d+1 colors with maximum degree d.

SO! My main problem is: Do I need to draw the new edge to an existing vertex, or can I draw it to a new vertex? Any ideas? Am I going about this the wrong way? Thoughts and suggestions greatly appreciated!

• Is there a chance you could reduce this question to the root of the problem? – Jernej Mar 6 '13 at 7:02