Q1 (10 points)

Show that a simple undirected graph with 72 vertices and more than (n-1)(n-2)/2 edges is connected. [You may find the following result

useful: If G is a simple undirected graph with 72 vertices and p connected components, the maximum number of edges in G is

(n-p)(n-p+1)/2]