Prove by induction that every connected undirected graph with n vertices has at least n-1 edges

Solution 1:

HINT: Suppose that the result is false, so that there are graphs $G$ such that $|E(G)|<|V(G)|-1$. Among all such ‘bad’ graphs let $G$ be one with the smallest possible number of vertices, and let $n=|V(G)|$, so that $|E(G)|<n-1$. Let $v$ be a vertex of $G$ whose degree is as small as possible, and consider the graph $G\,'$ that remains when you remove $v$ and any edges attached to it. Clearly $|V(G\,')|=n-1$.

• What is the largest possible value of $|E(G\,')|$? (Remember, $G$ is connected; what does this say about $\deg(v)$?)

• Why does this contradict the way in which we chose $G$?

Note: This minimal counterexample approach is equivalent to mathematical induction in the version that most people learn first, and it’s often easier to use. The argument could be rephrased as a proof that if the theorem is true for graphs with $n-1$ vertices, it must be true for graphs with $n$ vertices.