Theorem A connected graph has n verticies and n edges Than t

Theorem: A connected graph has n verticies and n edges. Than the graph contains no more than one simple circuit. Prove this theorem.

Solution

The non-connected graph on n vertices with the most edges is a complete graph on n-1 vertices and one isolated vertex. So you must have one more than (n-1)n/2 edges to guarantee connectedness. It is easy to see that the extremal graph must be the union of two disjoint cliques (complete graphs). (Proof:In a non-connected graph with parts that are not cliques, add edges to each part until all are cliques. You will not have changed the number of parts. If there are more than two disjoint cliques, you can join cliques [add all edges between them] until there are only two.) It is straightforward to create a quadratic expression for the number of edges in two disjoint cliques (say k vertices in one clique, n-k in the other). Basic algebra will show that the maximum occurs when k=1 or n-1. (We\'re not allowing values outside that range.)

First a direct proof, then an induction proof:

Let the graph have n nodes, and the degree of each node be d[n].
The sum of the degrees is
d[1] + d[2] + .... + d[n] = 2 * number edges.

If all the degrees are different,
then the smallest they can be is
1 + 2 + 3 + .... + n = n (n+1) / 2

If that equals 2 * # edges, then # edges = n (n+1).

But the largest possible number of edges is
n (n-1) / 2 in the complete graph.

Therefore n (n+1) <= n (n-1) / 2
2n