Induction Proof of Algorithm [Greedy Graph Coloring]

algorithmscoloringgraph theoryinduction

Having a $G = (V,E)$ with each vertex having a range $[a,b]$.

Every two vertices are connected only if $[a_1,b_1]$,$[a_2,b_2]$ have a common subrange.

Each range of vertex is:

  • $rV1 = [0,5]$
  • $rV2 = [1,3]$
  • $rV3 = [2,10]$
  • $rV4 = [4,9]$
  • $rV5 = [6,7]$
  • $rV6 = [8,12]$
  • $rV7 = [11,13]$

Graph based on above ranges.

The Algorithm:

ranges = rV1,rV2,rV3,rV4,rV5,rV6,rV7...

COLOR_INTERVAL_GRAPH(rV1,rV2,rV3,rV4,rV5,rV6,rV7...){
if(number of rVi > 0){
 C_m  = MAXIMAL_COLOR_CLASS(rV1,rV2,rV3,rV4,rV5,rV6,rV7...);
 //paint C_m vertices with color m.
 //new_ranges <- remove C_m from rV1,rV2,rV3,rV4,rV5,rV6,rV7...
 return {C_m} U COLOR_INTERVAL_GRAPH(new_ranges)
 else:
   return []

MAXIMAL_COLOR_CLASS(new_range){
C = []
i = 1
while(i <= new_range.size()){
  C = C U {Vi}
  j = i+1
  while(j <= new_range.size() AND rVi (not common subrange with rVj)){
  j = j+1
i=j
return C

How to prove using induction that the algorithm uses the fewest possible colors.

After searching a bit i found that the MAXIMAL_COLOR_CLASS function in line 4 extends the C set.

I have to prove that the optimum coloring of any graph (of this type) can be transformed in order the first chromatic class is the same as the output of MAXIMAL_COLOR_CLASS.

Then using the above (by induction) i can show that every optimum coloring is the same as the output of the MAXIMAL_COLOR_CLASS proving the algorithm correct.

Not sure how to use induction to prove that.

Best Answer

Induction proof proceeds as follows:

Is the graph simple? Yes, because of the way the problem was defined, a range will not have an edge to itself (this rules out one of the easiest ways to prove that a graph is not n-colorable). Does it hold for 0 or 1 vertex? Yes, trivially. How about two vertices (with one edge, because disconnected vertices do not affect chromatic number)? You should be able to work out the justification for this step, and it is arguably the first non-trivial case and should be used as your base case.

Suppose you know that it holds for n vertices. Those vertices correspond to particular ranges. You could choose to prove that it then holds for n+1 vertices by adding another range (and an unknown number of edges) but this seems hard and potentially complicated. Instead, suppose it holds true for n edges. There are two ways that we could add an edge: by extending the endpoint of a nearby range until they intersect or by adding a new range entirely. Consider the output of the algorithm in either scenario, and you will have your proof.

In general, the more of your work you post, the better help you will be able to receive. This site is not intended to solve homework problems without some demonstrated effort and understanding or lack thereof.

Related Question