Dr Nicos Georgiou is a Lecturer in the School of Mathematical and Physical Sciences at the University of Sussex.
He's on TSR to present a series of maths challenges.... can you solve them?
Can you draw the following networks (also known as ‘graphs’) without lifting your pencil from the paper and without retracing an already drawn line?
To solve these problems, we need to go back to the 18th century and the mathematician Leonard Euler.
Euler is (among other things) known for solving the ‘Seven Bridges of Koningsberg’ problem and laying the foundations for graph theory in the process.
The Seven Bridges of Koningsberg
The city of Konigsberg had 7 bridges connecting the two islands of the river Pregel to the mainland and with each other.
The question Euler faced was whether one could walk over all bridges exactly once in a single stroll.
He worked out that he could make the problem simpler by eliminating all of the map’s features apart from the list of land masses and the bridges connecting them.
This leaves only an abstract ‘graph’, where each link represents a bridge and each ‘vertex’ represents a separate piece of land.
A graph (or network) is a collection of points (called nodes or vertices) and lines (called links or edges) that act as "bridges" between those points.
For example a triangle is a graph with three vertices (the corners) and three links (the triangle edges). The edges must always start and end at a node, they can't fly around disconnected. If we can count the number of vertices and edges (I.e. We don't have an infinite number of them) then we call that a finite graph.
The question is now translated into "Can we draw this without lifting our pencil
and without retracing our steps?" Any graph that has this property is called an Eulerian graph.
It turns out that the answer to this question – whether a graph is Eulerian or not – is only related to what is called the ‘degree’ of the vertices. The degree of a vertex is just the number of links that touch it.
For example, in the Konigsberg problem, the degrees are 5,3,3,3 for A;B;C;D respectively.
Euler presented a solution that can be summarised in the following theorem:
Any (finite) connected graph is Eulerian if one of the following conditions
1) Each vertex has an even degree, i.e. each degree is a multiple of two. If this is the case then we can say that the graph has an ‘Euler circuit’.
2) There are precisely two vertices with an odd degree (and any potential path must start at one of these two vertices and end at the other one). If this is the case then we can say that the graph has an ‘Euler path’.
The theorem only tells us whether a graph is Eulerian or not – it is a different story to actually draw it in an appropriate way.
However, once we know we are not wasting our time, we can try and draw it. Efficient algorithms exist, in order to draw the graph properly (or even ask a computer to do it).
You can try and search for Hierholzer's algorithm (1873) and see if you can use it yourself.
Can you solve the graphs?
Can you find the correct routes through the graphs, and draw the shape without retracing your steps? Post your answers in the comments below (use spoiler tags!)
A bit stuck?
There is a solution: B → C → D → E → A → B → D → A → C
Notice that the degree of the vertices A;D;E is even (4; 4; 2) respectively, but the degree of B and C is 3 and odd. According to the discussion above, any potential loop must start at either B or C and end at the other one. In this solution we started from B and ended at C, but we could have done it the other way too. For example, read the solution backwards :-)
If you check the degrees of the various vertices, vertices A, B, E and H have an odd degree; 3,3,5,5 respectively. Since there are more than two vertices of odd degree this graph cannot be drawn without retracing a line or without lifting the pencil.
However, if you remove a single link (edge), then it is possible. This problem has two different solutions. Can you find the extra link?
Again, check the degrees of all of the vertices. All of them are even; K has
degree 10, A, and B degree 2 and the rest degree 4. So the graph can be traced without lifting your pencil, and in fact it can be done starting from any vertex you like.
A possible solution is:
K → C → F → K → J → G → K → D → I → K → E → H → I →
→ J → C → D → E → F → G → H → K → B → A → K