In 1735 a famous mathematician by the name of Leonhard Euler solved a problem known as the Konigsberg Bridge problem. The general idea is that the city of Konigsberg has seven bridges connecting four pieces of land that are separated by a forked river passing through. The challenge is to determine whether or not it is possible to reach all four sections of land by passing over each bridge exactly one time.
The situation in Konigsberg looked something like this (bridges outlined in two shades of purple):
However, Euler redrew the problem using dots to represent the land, and edges to represent the bridges.
By abstracting the landscape into these two ideas that are key to the challenge at hand, he was able to prove that the number of bridges must be an even number in order to cross each bridge one time and reach all parts of Konigsberg. Thus, with seven bridges, it is not possible.
When Euler redrew the land and bridges of Konigsgberg, he created what is now known in graph theory as a “graph”. In graph theory, graphs look more like Euler’s graph than like the graphs we see in most math classes. They consist of nodes (dots or vertices) connected by edges (lines or curves) that represent the key parts of a problem.
By simplifying a situation down to nodes and edges, we can solve a range of problems, many of which are particularly valuable in computer science.
Take, for example, social media. One of the goals of many social media sites is to “connect” a person with a person or place that she might be interested in. Imagine a girl by the name of Samantha that has seven friends on a social media site such as Facebook. These sites try to connect people to other people that they may know or have interest in. They do this by giving friend recommendations. These recommended friends are people that Samantha is not connected with on Facebook, but with whom many of her Facebook friends are connected to. Facebook “thinks” that if several of Samantha’s friends are all friends with a certain person, then perhaps Samantha might know this person also and want to become Facebook friends with her or him. This situation can be modeled with the following graph and pseudocode.
Graph:
Pseudocode:
If a stranger is friends with more than two of Samantha’s friends, suggest to Samantha that she becomes friends with that stranger. If the stranger is friends with two or less of Samantha’s friends, do not suggest that Samantha become friends with that stranger.
Samantha would be asked if she would like to become friends with Stranger 1, but not with Stranger 2. Of course, this is not exactly how Facebook’s algorithm reads, but it is likely somewhere along these lines.
Graph Theory Games
Analyzing graph theory can get complicated fairly quickly, but there are quite a few fun games that we can play that involve this branch of mathematics. One such game is called Sprouts. It was invented by John H. Conway and Michael S. Peterson both at the University of Cambridge in the United Kingdom. Possibly because it can be enjoyed by children on up through highly analytical adults, Sprouts quickly became a popular game.
What to give Sprouts a try? Grab a pencil, paper, and a friend. Draw as many dots as you like on the paper (between 3 and 6 is good for the first round). We will use four dots in our example:
The first player starts by connecting any two dots. She could also choose to draw a loop that starts and ends on the same dot. The two images below show valid moves.
 |
 |
The first player then makes a new dot somewhere toward the middle of the line/curve she just drew (it doesn’t matter exactly where).
Now it is the other player’s turn to connect two dots (or loop around one dot), and place a new dot toward the middle of the connecting line. Play continues as such, with just two rules:
- A dot can never have more than three lines attached to it
- Lines are never allowed to cross one another.
Here are possible moves for the next three plays:
 |
 |
 |
The last person who is able to draw a line between dots without crossing another line or exceeding three lines attached to any one dot wins.
After continuing our example for quite a few rounds, we are left with the following situation in which there are no more possible plays.
When we play Sprouts, we are actually creating a graph. And just as graphs made from nodes and edges help software engineers analyze a problem, we can analyze our game. For example, we might wonder if it is possible to make a game of Sprouts continue on forever without an end.
To answer this think about a relatively small game of Sprouts that starts with two nodes.
Each node has the possibility of connecting to three edges.
But once we connect the two dots with one edge, we eliminate two of our six original moves.
Next we add a new node to our connection. This node is already connected to two nodes, so it has just one more connection left.
All in all, after our first move, we have eliminated two possible moves and added one new move, leaving a total of one less move than we started with. This continues as the game is played, with each move reducing the total possible number of moves by one. Since we start with a given number of possible connections and reduce that number by a total of one with each move, eventually the game must end. We can use similar approaches to figure out the most possible moves in a game, the least possible moves, and even whether the first or second player has an advantage.
Sprouts is one of many fun games that have a foundation in graph theory. Games such as Ticket to Ride, Settlers of Catan, Hex, and Sim (a pencil and paper game) can all be represented and analyzed using graph theory. Want to learn more? Take a look at some of the great sites linked below!
Learn More
Sim
https://en.wikipedia.org/wiki/Sim_%28pencil_game%29
Downloadable Graph Theory Games
https://www.tes.com/teaching-resource/graph-theory-puzzles-and-games-12164908
Sprouts
http://pi.math.cornell.edu/~mec/2003-2004/graphtheory/sprouts/howtoplaysprouts.html
Graph Theory Games
https://open.ed.ac.uk/graph-theory-puzzles-and-games/
Graph Theory
https://www.youtube.com/watch?v=ZQY4IfEcGvM
Graph Theory Applications
https://www.britannica.com/topic/graph-theory
Koenigsberg
https://medium.com/brandons-computer-science-notes/graph-theory-3bd99b24fa2a
Example of graph theory
https://www.freecodecamp.org/news/i-dont-understand-graph-theory-1c96572a1401/
Beanz Konigsberg
https://kidscodecs.com/7-bridges-konigsberg/
Beanz Graph Theory
https://kidscodecs.com/graph-theory/
