First of all, a convention. Let $(V,E)$ be a graph with degree function $\operatorname{deg}:V\to\mathbb{N}_0$. There are three results which get referred to as the Handshaking Lemma
- $\sum_{v\in V}\operatorname{deg}(v)=2|E|$,
- $\sum_{v\in V}\operatorname{deg}(v)$ is even,
- the number of nodes of odd degree is even.
I am using the third one (of course we can get to the third from the other two, readily).
I am teaching some graph theory and I had it in my head that in my undergraduate there was an odd-sounding "everyday" application of the Handshaking lemma.
In class I gave the following. Let $V$ be a set of people and draw an edge between siblings ($x$ and $y$ are siblings if $x\neq y$ and the set of parents of $x$ is equal to the set of parents of $y$).
The handshaking lemma implies that the number of people in $V$ who have an odd number of siblings in $V$ is even.
This was a bit underwhelming in class because the people in $V$ with an odd number of siblings, well, look at $x\in V$ and its set of neighbours $N(x)$… well $|\{x\}\cup N(x)|$ must be even and the thing falls out that way too… maybe I undersold this, I don't know.
Well anyway, I rustled up my old undergraduate notes and lo and behold the great confounding example that made my eyes light up was just this one… (there was another example but it was actually a non-example: Must the number of families with an odd number of children be even?… this is not true… unless there is some weird definition of family).
So now I am wondering are there any particularly odd or "cool" "everyday" applications of the handshaking lemma to win back these students?
Question: What are some odd/weird/cool/strong/counter-intuitive applications of the handshaking lemma that could be stated to the person on the street? Are there any?
Best Answer
Tired of being red and blue, the US states decided to become green and yellow: those that have an even number of neighboring states are green, those that have an odd number are yellow. Prove that there is an even number of yellow states.
Draw 9 intervals on the plane so that each interval intersects exactly three others. [This is not possible because the graph whose vertices are intervals and whose edges are intersection points would have 9 odd vertices.]
A mathematician was abducted by aliens and woke up on a tiny island surrounded by fog. Seven bridges could be seen leading from the island into the mist. A large sign read: This is the Foggy Lake. It contains 74 islands, some of which are connected by bridges. Seven bridges leave the Main Island; four bridges leave every other island. The mathematician reads this and sighs with relief: "Well then, there must be a bridge that leads to the shore, and I can find it". Why is he so sure? [We don't know if all the islands are connected to each other, but the connected component of the Main Island must have another odd vertex, which can only be the shore.]