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?
Best Answer
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?