# How many edges in a graph with $n$ vertices are needed to guarantee it is connected?

A graph $G$ is connected if every pair of vertices in $u,v\in V$ is connected by some path.

For an undirected graph with $n$ vertices, how large does the edge set $E$ have to be to guarantee that it is connected?

I know for the complete graph $K_n$ has precisely $|E| = \frac{n(n-1)}{2}$ edges, but surely we do not need to consider every one of these to guarentee that $G$ is connected do we?

• Think about how many edges you would have to remove from a complete graph to make it become disconnected. It seems clearer to view the problem from this direction. – mlg4080 Apr 29 '15 at 4:42
• Well, assuming you were disconnecting a single vertex you would have to detach $n-1$ edges (where $n$ is the number of vertices) from the vertex. So to guarantee connection, you would need $\frac{n(n-1)}{2}-(n-2)$ edges? – Groups n' Stuff Apr 29 '15 at 4:50

HINT: Note that the disjoint union of $K_{n-1}$ and $K_1$ is a graph with $n$ vertices that is not connected, so you need more than $\frac12{(n-1)(n-2)}$ edges. This graph is missing just $n-1$ of the edges of the graph $K_n$. Suppose that you remove fewer than $n-1$ edges from $K_n$; can you disconnect the graph?
Consider $K_{n-1}$ plus an isolated vertex. How many edges are there so far?