Page 278 Exercise 7

An undirected graph with only one vertex is connected.  Such a graph has 0 edges.  Adding a second vertex to this graph requires an additional edge to connect the first vertex to the second.  As each additional vertex is added we must add one edge
to connect the new vertex to one of the previous vertices.  If this is not done the resulting graph is not connected.   The figure
below shows the growth of a graph from one vertex to four. With  each addition, only one new edge is required.

We can demonstrate that the above observation holds for all graphs.  Assume that N = number of vertices and E = Number of
edges, then formally a graph is connected:
1. If N=1, and Edges_n = 0

2. For N > 1,  Edges_n = 1 + Edges_n-1 

 
Proof: Assume that we have a graph G as given below.  We remove an edge from this graph. This produces the two Graphs G1
and G2  (also below). The number of edges in G must equal E1+E2+1 since G1 and G2 were produced by removing a single edge from G.  By rule 2, E1=(N1-1) and E2=(N2-1).  Therefore, E = N1-1 + N2-1 +1 = N1 + N2-1 =  N-1.

 
PART B: A strongly connected digraph requires a minimum of N edges.  The samples below show that all of the resulting graphs are cyclic.

To prove this we use the result of the previous exercise, we know that removing an edge from a graph with N-1 edges produces a graph which is not connected.  This means that graphs with N-1 edges cannot have cross paths. Removing an edge from a graph with N edges, however, does not produce an unconnected graph as the above examples illustrate.  Since no connected graph with fewer than n edges can be cyclic, the examples in are trees.