Twenty Followers & The Handshaking Theorem
Well that didn’t take too long. Howdy, everyone! Feeling pretty welcome around these parts.
If we were all to shake hands, how many handshakes would occur in all? Pictured below is the complete graph on 20 vertices; every vertex is joined to every other one exactly once. The number of edges here is how many handshakes would occur among all of us.
Quite a few! There’s a shortcut called the Handshaking Theorem (some relegate it to the status of a Lemma, but I think it’s nice enough to call a Theorem) to help us count them all. It says that summing up all the degrees in the graph gives us twice the number of edges:
What’s the proof? It makes a lot of sense if you think about it: if a vertex has degree n, that means there are n edges attached to it. But any given edge is attached in two places (possibly the same vertex if it’s a loop). Therefore, summing up all the degrees across the whole graph ends up counting each edge twice.
In the complete graph on k vertices, any vertex has degree k - 1, so the sum of all these degrees is k(k - 1). Setting k = 20 and dividing the last expression by 2, we find that 190 handshakes would occur among us. Good thing we’re not actually going through with it.
edit: by the time I finished this post I already had two more followers. That would make 231 handshakes!
