Bridge issues
When you cross a bridge, what crosses your mind? Do you think about the weather, about your shopping list, or do you wonder whether you will catch the train?
Maybe you ask yourself: can I cross every bridge in the city once, and only once, on a single walk? While the last scenario may seem unrealistic to some, it is actually a famous question. When the problem was partially solved in the 18^{th} century, it sparked an entire new field of mathematics: graph theory.
Connecting the dots
“Graph theory is a huge branch of mathematics, but ultimately it’s about nothing more than dots connected by lines,” says Steven Kelk (Associate Professor at DKE, Faculty of Science and Engineering), who works in the field. “The origin of graph theory is widely attributed to a question that a famous mathematician, Leonhard Euler, worked on. He studied a problem called the Seven Bridges of Königsberg. At that time, the city of Königsberg had seven bridges connecting parts of the city. In 1736 Euler proved that, no, you cannot walk every one of those bridges once, and only once.”
Euler’s approach to the problem was a breakthrough. Kelk: “This is the first time that people abstracted something into a graph. Euler represented each of Königsberg’s landmasses as a dot, and each bridge as a line. He then showed that, if we want to cross each bridge once, then aside from the starting point and the endpoint, every dot must have an even number of lines connected to it. In Königsberg, all landmasses have an odd number of bridges, so it is certainly not possible”
Left: the bridges of Königsberg. Bridges are drawn as blue lines, the water is shaded in red. The drawing on the right depicts the situation as a graph, where the dots represent landmasses and the lines again represent bridges. The red numbers mark the number of bridges connected to each landmass. Can you cross each bridge once, and only once? You can’t, and that’s because there are too many landmasses connected by an odd number of bridges. Kelk: “If you have a dot connected by three bridges, for example, then you come in one way and leave in another. But when you come back via the remaining bridge, you’re stuck. That means you can start or end your walk on such a landmass, but if you have to pass through it? It’s not possible.” 
From 1736 to 2019
Modernday graphs can be much more complex, and they are often analyzed by computers. Kelk: “A famous example that we see today is the abstraction of ‘friends’ on social networks. People are shown as dots, and the lines between them mean that they know each other. There’s a vast amount of information in these graphs. You can ask all kinds of questions about them, and although I don’t work on social networks, this gives an idea of what my research is about.”
Really, really hard problems…
In particular, Kelk is drawn to questions that are very hard to answer with a computer. He proves this difficulty, and then chips away at finding mathematical shortcuts that help algorithms solve the problems more efficiently.
“If I’m good at one thing, it’s proving that a problem is hard. I love that. It’s a special kind of proof technique that I’ve always enjoyed. You also have to be really creative to solve hard problems. Most standard design techniques and algorithms don’t work, so you have to think about how to push the limits of what your computer can do.”
"Most standard design techniques and algorithms don’t work, so you have to think about how to push the limits of what your computer can do.”
…in biology
Kelk currently studies ancestral trees, which are used in biology to visualize the relationships between various organisms. The trees are constructed based on analysis of DNA sequences, but different analyses produce different results. “One tree might say species A and B were close relatives, while another might say that species A and C are closer. I calculate how different those trees are from each other. It turns out that, via some tricks and transformations, that’s a graph theory problem. Many people don’t see it as such.”
“I find it fascinating to approach it that way, because there is so much work on graphs. I can take all the heavy instruments that graph theorists developed in the last 300whatever years, and use them to solve these problems. On the other hand, many graph theorists don’t think much about applications. I mainly find this problem interesting because of the bridge it builds between these two fields.” He pauses. “Another bridge, yeah.”
Lost bridgesMaastricht did lose a bridge, but much longer ago, in the 13^{th} century. Some 200 meters south of the St. Servatius Bridge, the river hides the sunken remains of a 1^{st} century Roman bridge. The archaeological site has monumental status, and it is marked by a statue of a lion on a pillar. However, according to Kelk – “quite good at proving that problems are hard” – Maastricht’s bridges offer no puzzles, sunken or not. “There’s only two landmasses, one on each side of the Maas. If you draw Maastricht as a graph and you ask: can I cross every bridge only once, then yeah, the answer is obviously yes. It doesn’t matter how many bridges there are.” 
Maastricht versus Königsberg
Scale model Maastricht 1748, commissioned by Louis XV, property of Centre Céramique, Maastricht
Centre Céramique, Maastricht
Avenue Ceramique 50
6221 KV Maastricht

Königsberg has changed quite a bit since Euler thought about its bridges in the 18^{th} century. Presently, the city is called Kaliningrad. All seven original bridges were lost during World War II, and only five of them were reconstructed.

On the other hand, Maastricht has gained a lot of bridges since the 18^{th} century. This is obvious from a scale model of Maastricht anno 1748, which is on display at Centre Céramique. It is a copy of a scale model commissioned by the French King Louis XV.

The model helped the French develop military strategies, but it has such rich detail that it likely also raised the king’s prestige.
More Math/Maastricht stories
Bridge issues
When you cross a bridge, what crosses your mind? Do you think about the weather, about your shopping list, or do you wonder whether you will catch the train?
A unique Dutch windmill
As it turns out, Dutch windmills are not just national icons. They also hold a unique position in the mathematical landscape.
Through Ariadne’s guidance
The modernday incarnation of an ancient Greek goddess is a software package that provides rigorous, mathematical certainty about problems involving change.
Hiding in plain sight
Signals are everywhere, and they contain a lot of information. However, it is not so easy to see or to extract this information.
The math games surrounding us
The cheerful statues of the Zaat Herremenieke are connected to hundreds of mathematicians worldwide, who work in a field called game theory.
Power dynamics
The ability to reason gives humans an edge over beings driven by evolution, like cancer cells or animals. The outcome of this power imbalance varies depending on where you look.
A matter of balance
The importance of fairness and balance is not to be underestimated. It comes with unique challenges, both on a mathematical and on a personal level.
Sint Jan’s feedback
Giving directions is an art. How do you give directions that are not only precise, but which also remain valid in whatever unforeseen situation comes up?
To learn or not to learn…
…that is not the question. At least, not according to Mathias Staudigl. He is more concerned with the how of learning in and outside of game theory.
Running up that hill…
…with no problems? Hill climbing isn’t straightforward, whether that is for someone taking on a snowy mountain or for a computer trying to find solutions in an abstract space.
Advanced problem solving
Did you ever stop to think whether you solved a puzzle in the most efficient way possible? Math is here to help, and you may want to pay special attention if you marshal trains for a living.
One plus one equals three
Biology and mathematics offer a lot to each other. One has all sorts of interesting data, while the other knows how to put it to work.