we discuss a few Olympiad Combinatorics problems from the chapters of the book by the same title.  

In a graph G with n vertices, no vertex has a degree greater than delta. Show that one can color the vertices using at most delta + 1 colors, such that no two neighboring vertices are the same color. 

History: As with most graph coloring problems, the chromatic number of a graph refers to the smallest number of colors for which a coloring of the vertices exists such that adjacent vertices receive different colors. In addition, we are reminded of the four color theorem which states that every planar map can be colored with four colors such that adjacent countries receive different colors. Laszlo Lovasz is accredited with bringing this graph theory to the forefront by introducing a complex geometry to a graph in such a way that the topology of the complex provides some information about the chromatic number of the graph. 

Problem understanding : The degree of a graph is the number of edges incident to the vertex, with loops counted twice. A regular graph is one where each vertex has the same number of neighbors i.e. every vertex has the same degree. In this problem we arrange the colors as 1,2,3… and use a greedy algorithm as follows. 

We arrange the vertices in an arbitrary order and color the first vertex with color 1. Then in each stage, we take the next vertex in the order and color it with the smallest color that has not yet been used on any of its neighbours. The greedy choice makes sure we are using the smallest number for the colors. Since any vertex cannot have more than delta neighbors  and the greedy choice is picking a color different from the node, we are guaranteeing the following two properties: 

1. No two adjacent vertices will have the same colors 

2. At most delta + 1 colors are used. 

The latter property follows from the fact that when a vertex v is colored different from the delta neighbors, there will be one color in the delta + 1 set that has not been used. Since the minimum of such colors is used for the vertex v, all the vertices are colored using colors in the set {1,2,3,…. Delta + 1} 

By saving the larger number colors when we really need them, we are using the colors from the smallest numbers and therefore they are bounded by the set 1,2,3, … delta + 1. 

The greedy choice property solves this problem while proving that the delta + 1 color suffices. 

void ChromaticColoring (Node vertex, int[] colors ) 

{ 

     If (vertex != null) 

    { 

        usedColors = [] 

foreach (Node v in vertex.adjacents()) 

{ 

   if (v.color != UNKNOWN) 

     usedColors.Add(v.Color); 

} 

Sort(usedColors); 

Var availableColors = Colors.except(usedColors); 

vertex.color = availableColors.min(); 

Foreach (Node v in vertex.adjacents()) 

{ 

ChromaticColoring(v, colors); 

} 

 } 

}