Science in the City was held in Valletta on September 28. The author, together with eight other local mathematicians, had an activity, entitled Fun Mathematics at one of the tables in the Science Fair section. The team presented a variety of straightforward games which are fun to play but have some interesting and important mathematics behind them. The aim was to demonstrate that mathematics is not only a marvellous tool (for science and other disciplines) but also an enticingly beautiful art.

The Königsberg graph, representing the seven bridges of Königsberg. PHOTO: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsbergThe Königsberg graph, representing the seven bridges of Königsberg. PHOTO: https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

By a graph we will not mean the usual plot but a set of vertices (points) and edges such that each edge connects two particular vertices. We call it a clique if every two vertices are connected by an edge. A clique on n vertices is denoted by Kn. Drawings of K4, K5 and K6 accompany this article. Two of the games were played on such drawings.

The aim of the first game was to determine whether the edges of K4 or K5 could be traversed in such a way that each edge is used exactly once (and the marker is not lifted off the paper!). A solution is called an Eulerian trail. A common surprise for visitors was that they could not draw such a trail on K4 but could easily do it on K5 despite being larger. In fact, one can figure out that K4 has no Eulerian trail. Leonhard Euler (1707-1783) solved the problem for any graph. The degree of a vertex is the number of edges at that vertex. Euler proved that a graph has an Eulerian trail if, and only if, the number of vertices of odd degree is either zero (in which case the end vertex has to be the start vertex) or two (in which case one odd-degree vertex is the start and the other is the end). This solved the famous Seven Bridges of Königsberg problem and laid the foundations of graph theory. By Euler’s result, among the graphs in the images, only K5 has an Eulerian trail.

Drawings of K<sub>4</sub>, K<sub>5</sub> and K<sub>6</sub>. Photo: https://en.wikipedia.org/wiki/Complete_graphDrawings of K4, K5 and K6. Photo: https://en.wikipedia.org/wiki/Complete_graph

The second game involves two players A and B taking turns colouring edges of Kn (say K5 or K6) blue or red. The aim of A is that an all-red or all-blue triangle is formed, and that of B is to avoid this. On K5, it is possible that B wins, for example, if the five internal edges are coloured red and the five external edges are coloured blue. However, A always wins if n is at least 6. A basic Ramsey-type result says that if n is at least 6, then, no matter how the edges of Kn are coloured, there is always a red triangle or a blue triangle (can you prove this?).

Ramsey theory is a mathematical area described as the study of “finding order in disorder”. It is named after the British mathematician Frank Ramsey.

Peter Borg is an Associate Professor at the Department of Mathematics within the Faculty of Science of the University of Malta.

http://staff.um.edu.mt/peter.borg

Did you know?

• If n people shake hands with each other, the number of handshakes made is n(n-1)/2. For example, 10 people produce 10x9/2 = 45 handshakes. Why? How can this be represented by a graph?

• Fun with digits: 12 + 3 – 4 + 5 + 67 + 8 + 9 = 100. Can you find another way of inserting pluses and minuses in the sequence 123456789 so that the result is again 100?

• Leonhard Euler, mentioned in the main article, proved that the infinite sum 1/(1x1) + 1/(2x2) + 1/(3x3) + … is pi squared divided by 6.

For more trivia, see: www.um.edu.mt/think

Sound bites

• A set G of vertices (points) and edges such that each edge connects two particular vertices is called a graph (see the main article). It is an abstraction of a network. A subset I of the set of vertices of G is an independent set of G if no two vertices in I are connected by an edge. Thus, an independent set is the opposite of a clique. I is irregular if its vertices have pairwise different degrees (the degree of v is the number of edges at v). The irregular independence number of G, denoted by air(G), is the size of a largest irregular independent set of G. A graph is planar if its vertices and edges can be drawn (on a plane) without edge crossings. Prof. Peter Borg (the author), together with his PhD student Kurt Fenech and Prof. Yair Caro (University of Haifa, Israel), established several sharp bounds for air(G) and determined the planar graphs G with air(G) = 1. Their paper, entitled Irregular independence and irregular domination, has been published online in the journal Discrete Applied Mathematics (DAM) and will appear in the special DAM issue dedicated to The Second Malta Conference in Graph Theory and Combinatorics.

For more sound bites, listen to Radio Mocha on Radju Malta every Monday at 7pm and on Radju Malta 2 every Thursday at 4pm.

Sign up to our free newsletters

Get the best updates straight to your inbox:
Please select at least one mailing list.

You can unsubscribe at any time by clicking the link in the footer of our emails. We use Mailchimp as our marketing platform. By subscribing, you acknowledge that your information will be transferred to Mailchimp for processing.