I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs?
1.a. Consider the undirected graph with vertices $A$, $B$, $C$, $D$, $E$, $F$ and edges $AB$, $AC$, $BD$, $CE$, $DF$ and $EF$ (i.e., the graph is the 6-cyle $ABDFECA$). What is the minimal number of colours needed to colour this graph?
1.b. Show how when considering the ordering $A$, $B$, $C$, $D$, $E$, $F$ of the vertices in the above graph, a greedy algorithm will find this minimal number, and find one other ordering where it will not.