Greedy algorithm help proofreading

See more:

algorithm

I have some questions already answered but i want to know if i can do better.Any help is appreciated.
I am trying to answer them showing my logical steps so far.

I have a simple graph G = (V,E) where each vertex has a range [a,b] and every two vertices are connected only if [a_1,b_1] and [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 Created based on above ranges.

Based on the algorithm below i have to color the graph.

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

Question 1: Show why the algortihm is greedy, and used it to color the graph given above.

Question 2: Prove using induction that the algorithm uses the fewest possible colors.

Question 3: Convert the algorithm from recursive to iterative form.

Question 4: Instead of MAXIMAL_COLOR_CLASS now the algorith uses FIRST_LAST_CLASS which outputs a set of vertices that has the vertex with the smallest starting range and the vertex with the biggest ending range (remember [start,end]), where the last is not crossing the first. Show an example where this form of algorithm uses more colors than needed.

What I have tried:

Answer 1: The algorithm cointains the 'greedy choice property' since it tries to paint the most each turn, by choosing the best solution to the current subproblem without caring about future problems or backtracking. (Is my reasoning correct?).

<a href="https://i.stack.imgur.com/mEynR.png"></a>Graph Colored (Is the graph colored correctly?).

Answer 2: 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.

Answer 3: MAXIMAL_COLOR_CLASS stays the same, the COLOR_INTERVAL_GRAPH is transformed to:

COLOR_INTERVAL_GRAPH(ranges){
m=1
while(ranges.size() > 0){
C_m = MAXIMAL_COLOR_CLASS(ranges)
matrix <- C_m + "," + m //meaning [[1,5,6],1] [[2,4,7],2] [[3],3] in the example above
sequence = remove the C_m vertices from sequence //(sequence - C_m)
m = m + 1
}return matrix

Answer 4: In the graph given above this algorithm needs 4 or 5 colors since each C set can have at most 2 colors, however we know the graph can be colored using 3 colors instead. (Is my reasoning correct?).