A graphy Christmas blog

Publish date:

“Merry Christmas and a Happy New Year” from the Graph Guild

This year has been one which most, if not all, of us will be glad to see the back of. To brighten up spirits, and to keep you entertained this festive season, in this blog I’m going to cover some interesting Christmas related mathematical facts.  To exercise those grey cells, there are also a few puzzles for you to try.

Figure 1: A Christmas Cactus Image reference: Shutterstock
Figure 1: A Christmas Cactus
Image reference: Shutterstock

The Christmas Cactus

If you love plants, or consider yourself to be a bit of a botanist, you may have a “Christmas cactus” on a table at home.  The Christmas Cactus is a type of cactus which blooms around the festive season (hence its name), producing lovely flowers in red, white, yellow, pink, or purple.

As well as being a lovely house plant, the “Christmas Cactus” is also the name for a particular type of mathematical graph.  In particular, a Christmas cactus graph is a special case of the “cactus graph”.

So, a cactus graph is a connected graph in which any two distinct simple cycles (ie a cycle in which the only repeated node is the first and last) have at most one node in common.  For example, Figure 2 shows a cactus graph whilst Figure 3 shows a graph which is not a cactus graph:

 

Figure 2 – A cactus graph
Image reference: Capgemini

Figure 3 – This graph is not a cactus graph
Image reference: Capgemini

 

Puzzle 1

Is the following a cactus graph?  If not, why not?

Figure 4 – Is this a cactus graph?
Image reference: Capgemini

 

The Christmas Stocking Theorem

Pascal’s Triangle holds many secrets and interesting patterns.  For instance:

  • The first diagonal is always the number 1.
  • The second diagonal is the positive integers, 1, 2, 3, 4, 5, …
  • The third diagonal shows the triangular numbers. A triangular number is a number which when represented by dots can form a triangle.  For example, the number 6 can be represented as:

Figure 5 – First 6 rows of Pascal’s Triangle
Image reference: Capgemini
Figure 6 – The triangular number 6 
Image reference: Capgemini

 

Now, the Christmas Stocking Theorem states that the sum of a sequence of numbers along any diagonal of Pascal’s Triangle is given by the number perpendicularly under it.  For example, consider the first 4 triangular numbers ie 1, 3, 6, and 10.  If we colour these four values in green, then the sum of these values (20) is shown in red.

Figure 7 – The Christmas Stocking Theorem
Image reference: Capgemini

Fermat’s Christmas Theorem

Perhaps best known for his famous “Last Theorem”, the mathematician Pierre de Fermat is also known for his “Christmas Theorem”. In a letter dated 25 December 1640, Fermat wrote to Marin Mersenne claiming that he had a proof for the following statement:

Any odd prime p can be expressed as the sum of two non-zero squared integers, if and only if, the prime is one more than a multiple of 4.

For example, as the prime 13 leaves a remainder of 1 after dividing it by 4, we can write:

Puzzle 2

Sadly 2021 is not a prime number, but 2017 and 2027 are both prime and are the nearest primes to 2021.  Is it possible to express 2017 and 2027 as the sum of squares, and if so, what are the values?

A (Covid Safe) Christmas party

It turns out that 6 is not only the magic number in the battle against Covid, but it is also the minimum number of people needed at a party to encourage conversation, at least if you want to guarantee that the party has either:

  • Three or more guests that are mutual strangers; or
  • Three or more guests that already know one another.

To understand why, let’s represent guests as nodes and let’s draw all the edges between all the guests.  In graph theory, such a graph is called a complete graph (because all the edges exist between nodes), and is shown below.

 

Figure 8: A complete graph with 6 nodes
Image reference: Capgemini

Now, you’ll discover that no matter how you colour the edges (say red if the guests know one another and blue if they don’t) you will always create either a red triangle (ie three people who know each other) or a blue triangle (three people who are strangers).

Figure 9: A blue triangle in this colouration of the graph
Image reference: Capgemini

It turns out that 6 is the smallest number that satisfies these constraints.  For instance, suppose we have only 5 guests.  It is possible to colour the edges so that we do not have 3 guests who know each other or 3 people who are strangers to one another – ie it is possible with a party of 5 to colour the edges in a way such that there is no red or blue triangle:

Figure 10: No red or blue triangles in this colouration of the graph
Image reference: Capgemini

Puzzle 3 – Drawing Santa’s house

The house of Santa Claus is an old German drawing game for children.  It is possible to draw Santa’s house using one line only – specifically you cannot take your pen off the page and you cannot repeat (or go over) the same line.

So one possible solution would be: 1 -> 4 -> 2 -> 3 -> 5 -> 4 -> 3 -> 1 -> 2

Figure 11 – Santa’s House
Image reference: Capgemini

If Santa now has a neighbour, is it possible to draw the following using the same rules?

Figure 12 – Santa with a neighbour
Image reference: Capgemini

 

Final thoughts

I hope you had a little fun with the puzzles, and I hope you learned a few interesting Christmas and maths related facts.  The answers to the puzzles are:

  • Puzzle 1. No, it is not a cactus graph
  • Puzzle 2. It is not possible to express 2027 as the sum of two squares.
  • Puzzle 3. It is not possible to draw figure 12 without retracing an edge.

If you have questions on the puzzles or the answers, or would like to know more about Capgemini’s UK Graph Guild, please email me at calum.chalmers@capgemini.com.

Season’s best wishes to you all!

 

Author


Calum Chalmers

Calum Chalmers is a senior data scientist in the Insights & Data practice, with over 20 years’ analytical and machine learning experience.  He first fell in love with graph theory when studying mathematics at Glasgow University and at the University of Warwick.

Related Posts

Consulting Services

7 examples of great product roadmaps

Date icon November 12, 2021

Product roadmaps come in all shapes and sizes – how do you choose the right one to convey...

Artificial Intelligence

Developing Explainable AI using inherently explainable machine learning models

Date icon August 5, 2021

Explainable AI is machine learning with a focus on how we can understand a models output,...

Artificial Intelligence

Capgemini sign Microsoft Partner Pledge for an inclusive and sustainable future

Date icon July 7, 2021

To recognise the impact of transformative technologies and support making a positive societal...