What Do Mathematicians Do?: An Overview of Undergraduate Mathematics

Jane and her friend Julia were invited to a small get together at their friend Julio’s place. When they arrive, they don’t really know any of the other four people (other than Julio) who seem to know each other EXCEPT one of the four coincidentally is Jane’s cousin, Elaine.

This type situations happen all of the time. If you’re sitting in a classroom, you’re in a similar situation right now. When you are with a group of people, you are a part of a mathematical structure known as a graph. Actually, any network (relationships, pipe systems, road maps, the internet, ...) can be represented as a graph.

We see graphs anytime we have a collection of items (We call them vertices or nodes.) and relationships between those items (We call the relationships edges.). In fact, it is by the vertices and edges that we define a graph.

Graph theorists study all sort aspects of graphs. We ask questions about the longest path of a graph, how easy is it to break up a graph with vertex or edge deletions, and if we can draw a graph in the plane without crossing any edges (among many others).

We’ll explore a few interesting graph theory questions here.

If we happen to find ourselves in Königsburg Prussia in the 18th century, we would see a city layout similar to the one in Figure 2.5.6. The Pregel river flowed through the middle of the city forming two islands. The part we care about, though, is the seven highlighted bridges.

This game peaked the interest of the incredibly brilliant mathematician, Leonhard Euler (1707-1783), and to solve this question Euler introduced the field of graph theory to the world. The Königsburg bridge problem is considered the to be the first instance graph theory historically. Like Euler, we can picture Königsburg as a graph by treating the bridges as edges and use vertices to represent each land mass.

What do we mean by a "tour" on a graph? First, two edges are incident if they share a vertex. We can say a tour is a sequence of incident edges. We want to find a tour that begins and ends with the same vertex. This type of tour is called an eulerian circuit.

Let’s take a tour on our new Königsburg graph, and each time we visit and each time we leave a vertex, we will give that vertex a point. For example, if we start at vertex \(v_1\) and travel to \(v_3\) and then to \(v_4\text{,}\) then \(v_1\) and \(v_4\) have 1 point each while \(v_3\) has 2 points.

As we keep touring through our graph, the points of a vertex tells us how many edges touching that vertex are a part of our tour.

From questions Question 2.5.10, Question 2.5.11, and Question 2.5.12, we see that a vertex will only have an odd number of points (or adjacent to an odd number of edges in our tour) if that vertex either starts or ends the tour... unless the tour ends where it started.

Remember that an eulerian circuit passes through EVERY edge and ends where it started. So can a vertex in an eulerian circuit have an odd number of points? No. So if a graph has an eulerian circuit, then every vertex is adjacent to an even number of vertices. We just drew up a sketch of a proof for the following theorem.

We finally see what Euler saw.

Let’s look again at the graphs in Figure 2.5.3. This time we want to break down our graphs by deleting vertices. In particular, we want to know how many vertices we have to delete in order to break the graph into pieces.

For example, if we delete one vertex from the first graph in Figure 2.5.15 (the edges adjacent to that vertex are also deleted), does our graph break into two separate pieces? No. It’ll take more than one vertex, but it can be done with two vertices! In Figure 2.5.16, we deleted two vertices (indicated by the red open circles), and now the graph is broken up. We say it is disconnected.

There’s a lot we could say about this situation. The two vertices we deleted are a cut set of the graph, and the pieces are called components. After we delete our cut set, if \(u\) is in one component and \(v\) is another component, then our cut set is a \(u-v\) separating set. In this graph, our cut set had two vertices, so we say the graph is \(2\)-connected.

So how connected are the graphs in Figure 2.5.15?

Knowing how connected a graph is can tell us other things as well. For example,

Connectivity and cycles do not seem to be immediately related, but graph theorists have discovered that they are related concepts.

Let’s play one more walking game. This time we’ll look at paths in a graph. A path is like a tour except now vertices can be revisted. So a path is a tour with unique vertices and edges.

The paths you found in Activity 2.5.2 are called internally disjoint paths since they have no vertices in common other than their endpoints. Did you find four internally disjoint paths in the graph in Figure 2.5.20? Good. For a graph \(G\) with nonadjacent vertices \(x\) and \(y\text{,}\) is there a way we could count the number of \(x\)-\(y\) internally disjoint paths in \(G\text{?}\)

In Activity 2.5.2, when we found our first \(v_1\)-\(v_5\) path, we deleted the internal vertices.

Does this give us some sort of link between \(x\)-\(y\) separating sets and the number of internally disjoint \(x\)-\(y\) paths?

Woah. So we had four internally disjoint paths and a separating set cardinality four. This is not a coincidence. Let’s take graph \(G\) with nonadjacent vertices \(x\) and \(y\text{,}\) and let’s call the number of internally \(x\)-\(y\) paths \(p(x,y)\text{.}\) Let’s also let \(c(x,y)\) be the cardinality of a smallest \(x\)-\(y\) separating set. Now we can show they are related.