# A Wolfram Notebook on Vizing’s Theorem: From Proof to Program

Vizing's theorem states that if is a simple undirected graph having maximum degree , then has a proper -edge-coloring. Here, a proper -edge-coloring is a coloring of the edges of from a palette of colors such that no vertex is incident to two or more identically colored edges. Note that at least colors are needed for a proper edge-coloring of , to provide enough distinct colors for edges incident to vertices of maximum degree. Combined with Vizing’s theorem, it follows that the edge-chromatic number of , which equals the minimum such that has a proper -edge-coloring, is either or . In this demonstration, we use the Wolfram Language to turn a proof of Vizing’s theorem into a program for giving any graph a proper -edge-coloring.

G

Δ

G

(Δ+1)

k

G

k

Δ

G

G

k

G

k

Δ

Δ+1

G

(Δ+1)

Let be a simple undirected graph. We proceed by induction on , the number of edges. If , then the theorem trivially holds. Let ; to illustrate the proof and our program, we will set as the complete graph on seven vertices.

G=(V,E)

m

m=0

m>0

G

graph=CompleteGraph[7]

In[1]:=

Out[1]=

Hence we have the following palette of “colors” to choose from...

colors=Range[Max[VertexDegree[graph]]+1]

In[2]:=

{1,2,3,4,5,6,7}

Out[2]=

... and for visualization purposes we'll associate them with the following actual hues.

colorAssociation=AssociationMap[Function[color,Hue[color/Length[colors]]],colors]

In[3]:=

1,2,3,4,5,6,7

Out[3]=

Suppose for each edge , there exists a proper -edge-coloring of the edge-deleted subgraph of . We’ll start out by working with the proper -edge-coloring of below (the other vertices are preemptively named for later convenience).

xy∈E

(Δ+1)

c

G-{xy}

G

(Δ+1)

c

G-{xy}

partialEdges={yy[2],yy[3],yy[4],yy[5],yy[6],y[2]y[3],y[2]y[4],y[2]y[5],y[2]y[6],y[3]y[4],y[3]y[5],y[3]y[6],y[4]y[5],y[4]y[6],y[5]y[6],xy[2],xy[3],xy[4],xy[5],xy[6]};partialGraph=Graph[partialEdges,VertexLabels"Name",GraphLayout"CircularEmbedding"];partialColoring=AssociationThread[partialEdges{2,4,1,3,5,5,4,7,1,7,1,6,6,3,2,6,3,2,5,4}];SetProperty[partialGraph,{EdgeLabelsNormal[partialColoring],EdgeStyleNormal[Map[colorAssociation,partialColoring]]}]

In[4]:=

Out[7]=

Iteratively extend the fan, starting with the vertex y, all neighbors of x available and 0 as the unused dummy color. Keep going until the fan can no longer be extended.

To find the Kempe chain, we iteratively apply our function until it can no longer find a new vertex to extend the path.

Here’s what our Kempe chain looks like.

We can put everything together into a single function.

We also define a function for checking if a given edge-coloring is proper.