Q1) Explain data and record structures for vertex ordering and vertex or edge coloring (or labeling) and suitably greedy graph search algorithm to solve each of the following problems in the time bound indicated. Illustrate each algorithm with vertex or edge coloring (or labeling) on a graph or tree designed to teach your algorithm. The graph (or tree) should have at least 18 vertices and a maximum degree of at least 4. The graph should be connected with a minimum degree 3.

iii) Determine a smallest-last vertex ordering and plot degree when deleted diagram for the given random geometric graphs:

a) G (20,0.25) [by hand],
b) G (400,0.15),
c) G (4,000,0.06).