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

The problem is in the title. Here is the hint given:

In the inductive case, try proof by contradiction. For this proof by contradiction, you may need to use the hand-shake lemma and concept of minimum degree. Show that the outcome of this proof contradicts the inductive hypothesis.

Not sure what it is meant by "concept of minimum degree" and how to apply the lemma. Any ideas?

-

1 Answer

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.

-
largest possible value of $|E(G\,')|$ is n-3? since deg($v$) is at least 1? Sorry if i didn't understand your hint; i'm a bit slow when it comes to math. –  uohzxela Nov 14 '12 at 13:01
@uohzxela: Yes: $|E(G\,')|\le n-3$, since $|E(G)|\le n-2$ and $\deg(v)\ge 1$. But $|V(G\,')|=n-1$, so $|E(G\,')|<|V(G\,')|-1$. This means that $G\,'$ is a ‘bad’ graph with fewer vertices than $G$. Why is that impossible? –  Brian M. Scott Nov 14 '12 at 13:10
Is it impossible simply because $G$ is already defined as the 'bad' graph with the $smallest$ number of vertices? Hence there's a contradiction right. Ok i get it, but this is quite an unintuitive way for me to prove this problem. Is there any other way to prove using hand-shake theorem and concept of minimum degree? –  uohzxela Nov 14 '12 at 13:23
@uohzxela: Exactly right. I have finally thought of a way that fits the hint, but it’s unnecessarily complicated. Again let $G$ be a smallest ‘bad’ graph, with $n=|V(G)|$. If the minimum degree $\delta$ of any vertex in $G$ is $2$, the hand-shake theorem implies that $|E(G)|\ge|V(G)|$ and hence that $G$ isn’t bad, so $\delta=1$. Removing a vertex of degree $1$ and its attached edge decreases both the number of vertices and the number of edges by $1$ and leaves a smaller ‘bad’ graph, which is impossible. But there was no real need to reduce it to the $\delta=1$ case. –  Brian M. Scott Nov 14 '12 at 13:59
I see. You're right that the solution is unnecessarily complicated. I think the first proof is good enough for me. Thank you for the answers though, i learnt loads! –  uohzxela Nov 14 '12 at 14:22