proof of Vizing’s theorem (for graphs)
Proof of Vizing’s theorem (for graphs)
We must prove, for any integer , the following: if is a graph all ofwhose vertices have valency , then its edges can be colored (withadjacent edges receiving different colors) in no more than colors.
This form of stating the theorem allows us to do induction on thenumber of edges. A graph with zero edges, for instance, certainly doesn’tneed more than colors. Now assume (for any given ) thatall graphs with edges can be thus colored. For any graph with edges we choose an edge to remove, color the remaining edges, andtry putting the edge back.
Another way of looking at this: suppose there was (for a certain ) agraph with edges that could not be colored thus. There would thenbe a largest number , bounded by , such that all graphs with edges can still be colored thus. Then there would also be a with edges that cannot. Choose one of its edges and proceed as above. This time,succeeding in coloring
it after all would prove by contradiction
that therewas no such and hence no such .
Either way we have our where after picking an edge we can color everythingexcept that edge, and fitting it in too proves the theorem. Let the edge tofit run between v and . Some terms:
- •
With a palette of edge colors, and no more than edgesat any vertex, each vertex has at least one missing color.
- •
Let a Kempe chain
be any connected component
of thesubgraph
formed by all edges colored or . This is either acycle of even length, or an open path terminating at two verticeswhere one of or is missing.
Step 1. If there is a color missing both at v and at , usethat color for the edge and we’re finished.
Else, let color be missing at v (but present at ), and color be missing at (but present at v). If the Kempe chain ofcolors and that terminates at v is disjoint from the oneterminating at , swap the colors in the latter chain, then use for edge and be done.
Else it’s the same chain, in which case we proceed as follows.
Find the -colored edge from v, call it. Steal color from it and give it to edge , now is the problem edge that needs a color.
Go back to Step 1 calling it Step 2, replacing subscripts by in all text. This involves a color that was missing at (remains the missing color at v). If v and are awkward too,being in the same chain
find the -colored edge , give its color to making the problem:
Next time round (Step 3) increase the subscripts again.And if still necessary, transfer the color again.
Sooner or later (if we don’t get to bail out at one of the Steps) we will runout of colors, in the following sense: the color missing at some is not some new color but a color we’ve seen before (it can’tbe , that’s present at ). And not only is but also because is the color we just stole from .
A chain runs from v to and all its verticesexcept have color . Now isn’t (because ) nor one of the other vertices of the chain (becauseit doesn’t have color ). So isn’t on this .
does have color so it’s on some other disjointfrom . This could be as short as a single -colored edge orlonger, it doesn’t matter.
Swap the colors in that . Now use to finally color (merging and in the process).
This is in essence the proof usually given, as taught to students and found for instance in references [FW77] and [Wil02] of thehttp://planetmath.org/node/6930parent entry.