A) Finally, lets colour the map of Malaysia represented by graph G1. But first we need to introduce the definitions for the chromatic number and Four Number Theorem. The chromatic number, k of a graph G is the least number of colors needed for a coloring of this graph. The chromatic number of a graph G is denoted by (G). (Here is the Greek letter chi.) The Four Colour Theorem states that the chromatic number of a planar graph is no greater than four. Using the Greedy Colouring Algorithm find (G1). State the algorithm (In words, not in programming languages such as Python or C++) and indicate the order of which you coloured the vertices on (You need to redraw G1 here). Indicate also the number for each colour that you have used on G1. Why cant we colour the graph using colours less than (G1)? Does the algorithm guarantees of finding optimal (G1) ?

Perlis Kangar Sabah Kedah Kelantan O Alor Setar Kota Kinabalu O Kota Bharu Pes George Town Pulau Pinang Kuala O Terengganu Terengganu Sarawak Ipoh Perak Kuantano Kuching Selangor Pahang Shah Alam Seremban Negeri Sembilan Bandar Melaka Melaka Malaysia Johor Johor Bahru o Perlis Kangar Sabah Kedah Kelantan O Alor Setar Kota Kinabalu O Kota Bharu Pes George Town Pulau Pinang Kuala O Terengganu Terengganu Sarawak Ipoh Perak Kuantano Kuching Selangor Pahang Shah Alam Seremban Negeri Sembilan Bandar Melaka Melaka Malaysia Johor Johor Bahru o