# Prove that if $G$ is a graph with $n$ nodes and no loops or double edges and more than $\binom{n-1}{2}$ edges, then $G$ is connected.

Prove that if $G$ is a graph with $n$ nodes and no loops or double edges and more than $\binom{n-1}{2}$ edges, then $G$ is connected.

This is an exercise in Lovasz' Discrete Mathematics book.

-
You need one more edge, i.e., $\dbinom{n-1}2+1$. – user17762 Apr 24 '13 at 17:55
You also need that there are no loops or double edges. Maybe that is part of your definition of a graph, sometimes that is a simple graph. – Ross Millikan Apr 24 '13 at 18:00
Oops. Thanks user17762. – user43666 Apr 24 '13 at 18:00

You need one more edge, i.e., $\dbinom{n-1}2+1$. The proof falls out immediately using contradiction. Assume that the graph is disconnected. We can then find two sets of vertices $A$ and $B$ with no edges running between them. The maximum number of edges in this graph is $$\vert E \vert = \dbinom{n_A}2 + \dbinom{n_B}2$$ where $n_A \geq 1$ is the number of vertices in $A$, $n_B \geq 1$ is the number of vertices in $B$ with $n_A + n_B = n$. We then have $$\vert E \vert = \dfrac{n_A(n_A-1) + n_B(n_B-1)}2 = \dfrac{n_A^2 + n_B^2-n}2$$ Find the maximum of this function with the constraint $n_A, n_B \geq 1$ and $n_A + n_B = n$. I trust you can take it from here.