5
$\begingroup$

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 Answers 1

3

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)|. 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.

  • 0
    @uohzxela: You’re welcome!2012-11-14