Part 1 – What are Graphs?

Mathematics is full of fascinating ideas and concepts. These can, however, be very challenging to tackle and make sense of, especially when you are put under pressure to answer questions about them! In this post, and those to come, I hope to share some insight into these concepts without getting too formal. Where some definitions and more technical bits are introduced, they will be explained at end of the post: look out for the dagger symbols!

To begin, let’s ask what we do in mathematics. The first step in any area of maths is almost always to abstract things. We take some concept we want to be able to work with and pull out the essential ideas. From a bunch of maps we may take out just destinations and the routes between them; from 3D objects we may only need to know what ways we can rotate them and still see the same thing; from a collection of algorithms we may only care about how long they take to run on a computer, and so on.

(Figure 1: On the left, a roadmap with 3 places of interest. On the right, two diagrams abstracting it.)

In the figure above, we have a roadmap on the left, with places of interest and a road intersection marked by the letters A, B, C and D respectively. If we want information about which pieces of road some route covers, and how many times it does so, then the middle diagram tells us everything we need. This may seem a bit contrived, but imagine a Google street-view camera travelling the same pieces of road unnecessarily: over the course of photographing an entire city, the vehicle might waste days of time and petrol!

If we want to know only about how long the routes from place to place are, and don’t care if some travel routes may cover the same road twice, then the right diagram will suffice. We don’t want to consider as a destination if we are only concerned with the time to travel between our places of interest, so we don’t bother keeping it.

In both cases, we have taken a map with a lot of information we don’t need, and abstracted it into just some locations and connections between them (weighted connections in the second case). The first diagram is what we call a ‘graph’. The second, with the extra information about the length of the connections, we call a ‘weighted graph’ (since there are two connections between and , we may want to rather call it a weighted multi-graph if confusion can arise, as graphs we like to work with only have one or no connections between things).

With that exercise in abstraction behind us, we can now talk a bit about graph theory. Graph theory deals with mutual connections between things. The above example of locations and routes between them is just one of many where graph theory can be used. Formally, we say that a graph is an ordered pair of sets, . is a set whose elements are called vertices, these vertices are our ‘things’. is a set whose elements are called edges, these edges are our mutual connections between the things. Every edge is itself an unordered pair of vertices, indicating that the two things in the unordered pair are connected. For example, in the first diagram (in the middle) we have the vertices , , and , with edges , , and .

(Figure 2: For every pair of vertices, there are two possibilities: either the edge between them exists, or it doesn’t.)

At this point we should note that even though our original map had a lot of geometric information, like size and location, the graph we have made has none. The graph is just an ordered pair of sets. All we have left is a collection of four things, and a set of links between some of those things. With this in mind, note that all three of the pictures below are of the same graph. How we have chosen to arrange the vertices and edges doesn’t matter!

(Figure 3: 3 different ways of drawing the same graph.)

When two vertices in a graph are linked by an edge, we normally say that the vertices are adjacent. For example, in the graph of Figure 3 directly above (pictured 3 times), all of the vertices are adjacent to every other vertex. In Figure 2, on the left, and are adjacent, on the right they are not. To show a cute application of the idea in the next post, we’ll take a look at a graph of facebook, where vertices represent people, and two vertices are adjacent if the people are friends.

– an ordered pair is a list containing two things, whose order matters. So the ordered pair of numbers , is different from the ordered pair , even though their elements are the same. In a graph, we want to be clear about which set contains vertices and which contains edges, so we always have the set of vertices come first!

 – A set is just a collection of things, called elements. The collection of natural numbers less than 5 is a set, which we denote . Order and repetition don’t matter in a set, so is the same set as .

– An unordered pair is a list of two things, whose order doesn’t matter. The unordered pair of numbers is exactly the same thing as the unordered pair .