Mathman Explains: Topology to Graph Theory

 

This article is part 2 of a series where Mathman and I intuitively cover various topics in topology. If you don’t know what a topology is or what topological properties are, check out the first part of the series. Other than the basic topology covered in part 1, this article doesn’t assume that you know anything about graph theory!

1. So what is graph theory?
2. What is a graph?
3. How does graph theory relate to topology? 

 These feel like difficult questions to answer. We should try to look at the 3rd question first since we all know what a topology is. Maybe Mathman can help?

Interesting, so we can somehow represent a topology (the original map) with this 1D topological structure that retains how the bridges were connected. Lucky for us, this 1D topological structure is a graph! Much like how we make maps of the world, the connection between graph theory and topology is that we can represent topologies using graphs. So, what is a graph?

Figure 1: an example of a graph

Well, let’s look at figure 1 to get a better idea of what a graph looks like. As we can see, there are circles with numbers and lines connecting them. The circles with the numbers in them are called vertices. As we can see, there are 6 vertices in this graph!

The other part of the graph, the lines connecting the vertices, are called edges.

So what are these graphs used for? Well, as you will soon find out, graphs are all around you! Let’s look at some examples:

Figure 2: Molecules (Which are Graphs!)

One of the most common examples of graphs are molecules! As we can see, instead of representing the vertices as numbers, we represent the vertices as different colors depending on what molecule that vertex is. So, the vertices are the elements within the molecule and the edges are the bonds between each element! Looking at figure 2, we can see that K2CO3 (which is a salt!) has a double bond (there’s two lines instead of one). In graph theory, the edges between graphs are allowed to have different “weights”. For the double bond, we would say that the weight of that edge is 2. Now let's look at a different example!

Figure 3: Social Network Graph

Looking at figure 3, we see a graph where the vertices are the names of people. In applications like these, edges are the relationships between the vertices. So, the edges here could indicate whether or not these people follow each other on Instagram. So let’s do a little exercise:

1. Does Liz follow Vaidehi?
2. Does Ben follow Liz?
3. Do Liz and Vaidehi follow each other?

Since we define the edges as whether or not someone follows someone else, then we can look at the graph and see that there is an edge between Liz and Vaidehi. So Liz follows Vaidehi. Using a similar logic, we see that there isn’t an edge between Ben and Liz. So Ben doesn’t follow Liz. So do Vaidehi and Liz follow each other? Since there is an edge between them, then in this case we can say that they do.

However, this might not always be the case. It turns out that this graph is an undirected graph. What this means is that the relationship between two vertices goes both ways. So Liz follows Vaidehi and Vaidehi follows Liz. However, how would we represent if Liz followed Vaidehi but Vaidehi didn’t follow Liz back?

This is where we introduce directed graphs, which are the one way streets of graph theory.

Figure 4: Directed Graph Version of Figure 3

We represent directed graphs using an arrow as an edge. By making that edge an arrow, we can only “travel” from Liz to Vaidehi. So, this is how we would represent if Liz followed Vaidehi but Vaidehi didn’t follow Liz back.

Taking of all of this new information about graphs into consideration, let's look back at the bridge problem that Mathman was looking at earlier.

Secretly, we introduced a famous problem in graph theory called the Seven Bridges of Königsberg, where the goal is to try to find a path where you can cross all 7 bridges by only crossing each of those bridges once. As we can see from the graph, we have an unweighted, undirected graph, where the seven bridges are the edges and the four blue vertices are the four landmasses. Take a moment to try to think of a way that you would solve this problem...

Spoiler alert: there is no way to solve this problem! There is no way to cross all seven bridges only once! But how do we go about determining this more formally? Let's ask mathman about how we traverse graphs...

Now that Mathman has explained walks, let's get back to Seven Bridges of Königsberg. As a reminder, there are 4 landmasses and 7 bridges, where the goal is traverse the city in a way where we never cross the same bridge more than once. Sounds like we need to find a trail (open walk with no repeated edges). 

Turns out that there is a theorem we can use to determine if this is possible to solve. 

A graph can be traversed by single trail if it has 0 or 2 vertices of an odd degree.

What does odd degree even mean? Well, the degree of a vertex is the number of edges connected to it! So an odd degree means that there are an odd number of edges connected. Looking at the graph of the bridges, we can see that for each vertex, there are a odd number of edges connected to it. Since we have 4 vertices that have an odd degree, then it fails the theorem. So, the Seven Bridges of Königsberg problem cannot be traversed by a single trail! 

As you can see, graph theory is a fun field of mathematics that has a lot of applications from social networks to biology to even machine learning! We barely scratched the surface of the amazing theories and applications of graph theory, so we encourage you to go explore graph theory and to read our other blogs about it! 

In the next part of the series, we will be introducing a fun theorem about coloring maps (which connects to graph theory!)