Algorithms part II ex. 4.1.1 - riemann79/hello-world GitHub Wiki

What is the maximum number of edges in a graph with V vertices and no parallel edges? What is the minimum number of edges in a graph with V vertices, none of which are isolated (have degree 0)?

The maximum number of edges is 1 + 2 + ... + (V-1) = V(V-1)/2.

Proof

The first vertex can be connected to the remaining vertices with (V-1) edges. The second vertex can be connected to all the remaining vertices but the first one, since an edge was added in the previous pass. Thus, we have (V-1) + (V-2) edges. The third vertex can be connected to all the remaining vertices except for the first and second ones. Thus, we have (V-1) + (V-2) + (V-3) edges. For the same reason, the last vertex can't be connected to any previous vertices. Therefore, max = 1 + 2 + ... + (V-1).

The minimum number of edges is V-1.

** Proof **

Each vertex must be connected with one edge to at least another vertex that has no connections. In this way, the last vertex will be already connected. Thus, the minimum number of edges is (V-1).