6
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ To do the induction step, you need a graph with $n+1$ edges, and then reduce it to a graph with $n$ edges. Here, you only have one graph, $G$. You are essentially correct - you can take a graph $G$ with $n+1$ edges, remove one edge to get a graph $G'$ with $n$ edges, which therefore has $2n$ sum, and then the additional edge adds $2$ back... $\endgroup$ – Thomas Andrews May 5 '14 at 15:33
  • $\begingroup$ Side note: Better to use lowercase $v$ for vertices, because $V$ is often used for the set of all vertices. Capital letters for sets, lower case for elements is a good rule for clarity. $\endgroup$ – Thomas Andrews May 5 '14 at 15:35
  • 2
    $\begingroup$ Finally, this formalization is useless: $$\forall n \in \mathbb{N}, \sum_{V\;\in\;G} \deg(|V|) = 2|E|$$ Where is $n$ used? What you mean is, for all (finite) graphs,... (Also, why $\deg(|V|)$ rather than just $\deg(V)$ in your notation? What do the $||$ symbols mean here?) $\endgroup$ – Thomas Andrews May 5 '14 at 15:38
  • $\begingroup$ @ThomasAndrews Thanks for the feedbacks, I'll be careful! $\endgroup$ – torr May 5 '14 at 17:42
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I understand what is wrong and it feels great! thanks you mweiss! $\endgroup$ – torr May 5 '14 at 17:28
  • $\begingroup$ what you mean by smaller graph and lager graph, and what is the problem of adding a new edge in any kind of graph including a complete graph, it is allowed also , then in all cases the number of edges will be increased by 2 beacuse any edge is shared by to ends v1 and v2 ? $\endgroup$ – Tandee Holwa Jun 22 '15 at 15:52
2
$\begingroup$
  • ($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)$.

$\endgroup$
  • $\begingroup$ You need to be careful about "adding edges." You really want to remove an edge from the graph with $n+1$ edges. It's true that this is reversible, in this proof, but sometimes a forward construction in an induction proof like this doesn't hit all the $n+1$ cases. $\endgroup$ – Thomas Andrews May 5 '14 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.