Is my induction proof of the handshake lemma correct? (Graph Theory)

Question

I am an high-school senior who loves maths, I decided to taught myself some basic Graph Theory and I tried to prove the handshake lemma using induction.

While unable to find any proofs similar to the one I wrote on the Internet, I wonder if mine is incorrect or just presented differently. Any advice, remarks or critic would be warmly welcomed!

Let P be the following proposition "In any graph, the sum of the degrees of all vertices is equal to twice the number of edges:"

$$\textrm{P(n)}:\sum_{V\;\in\;G} deg(|V|) = 2n\;\;\;where\;\;|E| = n\\$$

Base case: $P(0): 2n = 0 |_{n=0}.$ Since there aren't any edge the number of vertices must be equal to $1$ or $0$.

$$\sum_{V\;\in\;G} deg(|V|) = deg(|V|) = 0\;\text{the number degree equal to }0.\\\text{thus, }P(0)\text{ is true}$$

Induction step: Assuming that $P(n)$ is true for a given natural number.Let show that $P(n)\Rightarrow P(n+1).$

$$P(n):\sum_{V\;\in\;G} deg(|V|) = 2n\\ \sum_{V\;\in\;G} deg(|V|) + 2= 2n + 2\\ \sum_{V\;\in\;G} deg(|V|) + 2 = 2(n+1)\\ which\;yield\;by\;adding\;two\;vertices\;of\;degree\;1\\P(n)\Rightarrow P(n+1)$$

$$\forall n \in \mathbb{N}, \sum_{V\;\in\;G} deg(|V|) = 2|E|\\ \textrm{For any given graph G, the sum of the degree of all vertices is equal}\\\textrm{to twice the number of edges.}$$

Thanks all, I really want to understand what is wrong (if anything!)

$$PS:\;Sorry\;for\;any\;grammar\;faults\;or\;horrible\;\LaTeX\;formatting$$

Answer 1

First of all, congratulations to you for your initiative in trying to teach yourself Graph Theory, and especially for trying to learn proof. That's really commendable.

One thing that a lot of people have trouble getting used to as they learn to write proof is that it is, primarily, a form of communication, not a means of computation, and for that reason a good proof is mostly verbal in nature, with equations and computations punctuating the sentences and paragraphs. The computations you are doing are (more or less) correct, but some of the ideas behind it are unclear (and possibly wrong). What I think is missing from your proof is a narrative, an explanation of what you are doing.

With that in mind, here are a couple of observations:

1. In the base case, you wrote "Since there aren't any edges the number of vertices must be equal to 1 or 0." Not necessarily; there could be any number of disconnected vertices in the graph. But since there are no edges, those vertices must all have degree 0, so the conclusion is still okay.
2. In the induction step, you want to go from a graph with $n$ edges (for which the formula is assumed to be true) to a graph with $n+1$ edges. You seem to be assuming that adding one new edge corresponds to adding two vertices of degree 1. But that might not be the case. It could be a matter of drawing a new edge between two existing vertices already in the graph, for example. The relationship between the set of vertices for the "smaller" graph and the set of vertices for the "larger" graph is unclear in your exposition. But (and this is the important thing) it doesn't matter. Adding a new edge will either require introducing two new degree-1 vertices or incrementing the degrees of two existing vertices by 1 or one of each of those. In any case the sum of the degrees goes up by 2.

So the argument is basically correct, at least as far as the sums goes and as far as the structure of a proof by induction, but the explanation of what is happening is lacking and a little bit confused when it comes to the interaction between the sets of edges and vertices.

But keep it up! This is a great attempt and I think you are off to a really good start.

Answer 2

• ($n=0$) "Since there aren't any edges the number of vertices must be equal to $0$ or $1$" - is unnecessary. The lemma is also valid (and can be proved like this) for disconnected graphs. Note that without edges, $\deg(v)=0$ for all vertices $v$ (if there is no ertex, one vertex, or many vertices), hence still $\sum\deg(v)=0$.

• Induction step. It seems that you start from an arbiotrary graph with $n$ edges, add two vertices of degree $1$ and then have the claim for this extended graph. However, this construction is not general enough: The resulting graph alsways has at least two vertices of degree $1$ and this is not true for a graph in general. Instead, you should have started from an arbitrary graph $G$ with $n$ edges; then obtained a graph $G'$ from it with only $n-1$ edges; then show hpw the vertex degrees in $G$ and in $G'$ are related; then use the induction hypothesis for $G'$ to show validity for $G$.

Off topic, I consider a direct proof without induction even more compelling: Consider the set of incidences, i.e. $I:=\{\,(v,e)\in V\times E\mid v\text{ is endpoint of }e\,\}$. Assuming no loops, for each edge $e$ there are exactly two vertices $v_1,v_2$ with $(v_1,e),(v_2,e)\in I$, hence $|I|=2|E|$. And for each vertex there are precicely $\deg(v)$ edges $e_1,\ldots,e_{\deg(v)}$ with $(v,e_1),\ldots, (v,e_{\deg(v)})\in I$. Hence $2|E|=|I|=\sum_{v\in V}\deg(v)$.