A Partridge in a Pear Tree

Actually, this is about a short history of graph theory which is not to be confused with those functions that you plotted at school all those years ago.  We shall look at pairwise counting, trees and twelve.

The beginnings of graph theory started in Koenigsberg, Prussia (now Kaliningrad, Russia).  In the eighteenth century there were seven bridges spanning the River Pregel.  The question was asked if it were possible to walk across each bridge just once during a stroll : –

The question was answered in the negative by Euler because each land mass (vertex) had an odd number of bridges (edges).  Parity is the quality of being odd or even in mathematics.

The above becomes the following as a graph : –

It cannot be done because all of the vertices have an odd parity.  If we add another bridge to change a couple of parities, then a Eulerian walk is possible.  We may walk across each bridge once if we begin at an odd vertex : –

If we add two more and make all the vertices have even parity, then a Eulerian circuit is possible.  We may begin and end at the same point : –

The Handshaking Theorem is also part of this branch of mathematics and is important at this time of year due to the Christmas party season.  You are the nth guest at a party; how many unique possible handshakes exist?  We assume that you shake hands with your host and each guest once and that you do not shake your own hand.

We can count it using C (n, k).  Read that as “n choose k”.  Since it takes two to shake hands we choose 2 and, because you don’t shake hands with yourself, we have

(n (n – 1)) / 2

If you are the twelvetyeth guest, then there are

(12 x 11) / 2 = 6 x 11 = 66

possible handshakes.

These numbers are actually the triangular numbers but with a different starting point to the sequence.  The triangular numbers are defined as

(n (n + 1)) / 2

Handshakes begin their sequence at 0 when n = 1 and triangular numbers begin their sequence at 1 when n = 1 : –

In the nineteenth century Cayley began counting a class of graphs called trees : –

The Cayley Formula is T_n = nⁿ⁻²

You will have a directory (a rooted tree) in your computer : –

The Four Colour Theorem was the first major computed-aided proof (Appel and Haken, 1976) : –

Now in the age of networks : –

We can have super spreaders, eg viruses or information : –

Or we can have super receivers, eg DDos attacks : –

Merry Christmas : –

There are 364 individual gifts in the song.