## Introduction

Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines and the internet, electronic circuits and even molecular bonds. There are also *social networks* between friends and families. All these systems consist of certain points, called **graphs**.

**Graph theory** is the study of graphs and their properties. It is one of the most exciting and visual areas of mathematics, and has countless important applications.

We can sketch the layout of simple graphs using points and lines. The position of points and the length of the lines are irrelevant – we only care about how they are connected to each other. The lines can even cross each other, and don’t have to be straight.

In some graphs, the edges only go one way. These are called **directed graphs**.

Some graphs consist of multiple distinct segments which are not connected by edges. These graphs are **disconnected**.

Other graphs may contain multiple edges between the same pairs of vertices, or vertices which are connected to themselves (loops).

For simplicity, in this chapter, we will only think about undirected and connected graphs without multiple edges and loops.

We can create new graphs from an existing graph by removing some of the vertices and edges. The result is called a **subgraph**. Here are a few examples of graphs and subgraphs:

The **order** of a graph is its number of vertices. The **degree** of a vertex in a graph is the number of edges which meet at that vertex.

Order:

Order:

Degree:

Degree:

Graphs which consist of a single ring of vertices are called **cycles** All cycles have

## Handshakes and Dates

You have been invited to an extravagant birthday party. After a rousing celebration the guests get ready to leave, and everyone shakes hands with everyone else. How many handshakes are there in total?

We can represent the handshakes using a graph: every person is

Rather than counting many edges for large numbers of guests, we could also try to find a simple formula that tells us the result for *any* number of guests.

Each of the *n* people is

${ handshakeTable(n) }

Unfortunately this answer is not quite right: we have counted every handshake

Therefore, the correct number of handshakes for ${n} guests is

The handshake graphs are special because every vertex is connected to every other vertex. Graphs with this property are called **complete graphs**. The complete graph with 4 vertices is often abbreviated as *K*_{4}, the complete graph with 5 vertices is known as *K*_{5}, and so on.

We have just shown that a complete graph with *n* vertices, *K _{n}*, has

*n*× (

*n*– 1)

On a different day, you are invited to a speed dating event for

In this case, the corresponding graph consists of two separate sets of vertices. Every vertex is connected to all the vertices in **bipartite graphs**.

The bipartite graph with two sets of size *x* and *y* is often written as *K _{x,y}*. It has

## The Bridges of Königsberg

One of the first mathematicians to think about graphs and networks was

The river Pregel divides Königsberg into four separate parts, which are connected by seven Bridges. Is it possible to walk around the city crossing every one of the bridges exactly once – but not more than once? You can start and finish anywhere, not necessarily in the same place.

Try to find a valid route by drawing on this map:

#### Map 1

#### Map 2

#### Map 3

#### Map 4

In the case of Königsberg it seems to be impossible to find a valid route, but some of the other cities do work. Euler managed to find a simple rule that can be applied to any city, without having to try lots of possibilities – using graph theory.

First, we need to convert the city maps into graphs with edges and vertices. Every island or region of land is represented by

Now the problem of “touring a city while crossing every bridge exactly once” has become a problem of “drawing a graph with one continuous stroke while tracing every edge exactly once”.

On paper, come up with a few different graphs and then try to work out which ones can be drawn with a single, continuous stroke.

Just like for the city maps before, we find that some graphs are possible while others are not. To help us understand why, let us label every vertex with its

**These graphs are possible:**

**These graphs are not possible:**

Comparing these numbers for graphs which are possible and those which are not possible, it seems that a graph can be drawn if it

If you scroll back to the map of Königsberg, you will find that there are more than two islands with an odd number of bridges. Therefore a route that crosses every bridge exactly once is indeed impossible – and this is what Leonard Euler discovered.

Euler’s discovery may not seem particularly useful in real life, but graphs are at the foundation of many other geographic problems, such as finding directions between two locations. We will discover more of these applications later.

## The Three Utilities Problem

Let us try another simple puzzle that is related to graph theory.

In a small village there are three utility plants, producing water, electricity and gas respectively, and three houses which need to be served. Unfortunately, due to the city’s layout, the pipes or cables for every product are not allowed to cross.

Try to connect each of the plants below to each of the houses, without any of your lines crossing:

Just like the Königsberg bridges before, you quickly discover that this problem is also impossible. It seems that some graphs can be drawn without overlapping edges – these are called **planar graphs** – but others cannot.

*K*_{3} is planar.

*K*_{4}

*K*_{5}

The *K _{5}* is the smallest graph that is not planar. Any other graph that contains

*K*as a subgraph in some way is also not planar. This includes

_{5}*K*,

_{6}*K*, and all larger complete graphs.

_{7}The graph in the three utilities puzzle is the *K _{3,3}*. It turns out that any non-planar graph must contain a

*K*or a

_{5}*K*or a

_{3,3}### Planarity

This is a planar graph, but the

## Euler’s Formula

All planar graphs divide the plane they are drawn on into a number of areas, called **faces**.

11 Vertices + Faces

15 Vertices + Faces

25 Vertices + Faces

When comparing these numbers, you will notice that the number of edges is always * F* +

*=*

**V***+ 1. This result is called*

**E****Euler’s equation**and is named after the same

Unfortunately, there are infinitely many graphs and we can’t check every one to see if Euler’s equation works. Instead we can try to find a simple

F | V | E |

0 | 1 | 0 |

**0** + **1** = **0** + 1

Any (finite) graph can be constructed by starting with one vertex and adding more vertices one by one. We have shown that, whichever way we add new vertices, Euler’s equation is valid. Therefore it is valid for all graphs.

The process we have used is called **mathematical induction**. It is a very useful technique for proving results in infinitely many cases, simply by starting with the simplest case, and showing that the result holds at every step when constructing more complex cases.

Many planar graphs look very similar to the nets of

This means that we can use Euler’s formula not only for planar graphs but also for all polyhedra – with one small difference. When transforming the polyhedra into graphs, one of the faces disappears: the topmost face of the polyhedra becomes the “outside” of the graphs.

In other words, if you count the number of **edges**, **faces** and **vertices** of *any* polyhedron, you will find that * F* +

*=*

**V***+*

**E**## Map Colouring

We have already used graph theory with certain maps. As we zoom out, individual roads and bridges disappear and instead we see the outline of entire countries.

When colouring a map – or any other drawing consisting of distinct regions – adjacent countries cannot have the same colour. We might also want to use as few different colours as possible.

Some simple “maps”, like a chessboard, only need two colours (black and white), but most complex maps need more.

When colouring the map of US states, 50 colours are obviously enough, but far fewer are necessary. Try colouring the maps below with as few colours as possible:

#### United States

#### South America

#### Germany

#### England

All of these maps can be coloured with only four different colours, but it is not hard to imagine that other, very complicated maps might need many more colours. In fact, some maps need *at least* four colours, whenever they contain four countries all connected to each other.

Like before, we can convert a map with countries and borders into a planar graph: every country becomes

Now we want to colour the vertices of a graph, and two vertices must have a different colour if they are connected by an edge.

In 1852, the botany student *all* maps. This turned out to be an extremely difficult problem, and became known as the **four colour theorem**.

During the following 100 years, many mathematicians published “proofs” to the four colour theorem, only for mistakes to be found later. Some of these invalid proofs were so convincing that it took more than 10 years to discover errors.

For a long time, mathematicians were unable to either prove that four colours are enough, or to find a map that needed more than four colours.

Little progress was made on the four colour problem until 1976, when

The four colour theorem is the first well-known mathematical theorem to be proven using a computer, something that has become much more common and less controversial since. Faster computers and a more efficient algorithm mean that today you can solve the four colour theorem on a laptop in just a few hours.

The four colour theorem only works for maps on a flat plane or a sphere, and where all countries consist of a single area.

However mathematicians have also looked at maps of *empires*, where countries can consist of multiple disconnected components, and at maps on differently-shaped planets, such as a torus (doughnut shape). In these cases you may need more than four colours and the proofs become even more difficult.

## The Travelling Salesman Problem

Let us think, once more, about networks and maps. Imagine that a delivery service has to visit

The delivery truck has to visit all cities, in any order. In the Königsberg bridges problem we wanted to find paths which travel along *every edge* exactly one. Now we want to find paths which visit *every vertex* exactly once. These paths are called **Hamiltonian cycles**.

There are countless different possibilities for Hamiltonian cycles in complete graphs. In fact, we can pick any vertex as starting vertex and then pick any of the remaining cities in any order:

Diagram coming soon…

Diagram Coming Soon…

In a graph with

- ${tsmString(tsn1)}

This means that, in total, there are ${tsnPaths(tsn1)} possible paths. A shorthand for this product is ${tsn1}! or ${tsn1} **Factorial**.

You could imagine that it might not be possible to travel directly between two cities - without going via another city. In that case we no longer have a complete graph, and finding the number of Hamiltonian cycles, if they exist at all, becomes much more difficult.

So far we have ignored the fact that some cities might be further apart than others. In real life, however, this is a very important consideration: we don’t just want to find *any* path but we want to find the shortest one. This is called the **Travelling Salesman Problem**. It has to be solved not only in transportation and logistics, but also when positioning transistors on microchips, to make faster computers, or when analysing the structure of

One simple method would be to try all possible paths, finding the length of each, and then picking the shortest one. However we have just shown that, even with just

Unfortunately there is no more efficient algorithm to solve the travelling salesman problem. Instead, mathematicians and computer scientists have developed various algorithms that find *good* solutions, even if they may not be the very best one. These algorithms, which only give approximate solutions, are called **Heuristics**.

Try rearranging the cities on this map. You can remove cities by clicking on them, and you can add cities by clicking anywhere on the map.

The **Greedy Algorithm** (or Nearest Neighbour Algorithm) is very simple: you start in a random city and consecutively move to the closest city you haven’t visited before. Once you have visited all cities, you stop.

Animation coming soon…

You can show that, on average, paths found using the greedy algorithm are 25% longer than the shortest possible path.

The **2-Opt Algorithm** starts with a random possible path. Then you repeatedly pick two edges and swap them around if that would reduce the length of the path. You stop when you can't reduce the length further by swapping any pairs of edges.

Animation coming soon…

It turns out that, long before computers even existed, Nature had found a clever way to find optimal paths between different locations: in ant colonies.

Ants want to find the shortest possible routes between their nest and possible food sources. They can communicate with each other through chemicals which they leave along their trail, and which other ants can follow.

- The ant colony sends out many scouts which initially travel in random directions. Once they find food, they return, leaving behind a trail of pheromone.
- Other ants tend to follow a trail when they find one, which leads them to food. On their return journey they deposit more pheromone, thus reinforcing the trail.
- Over time, pheromone evaporates. The longer a path is, the more time it takes ants to travel along it, and so the pheromone has more time to evaporate. Short paths, on the other hand, can get reinforced more quickly, so their strength increases faster.

Diagram coming soon…

Ant Colony System (ACS) algorithms try to replicate this behaviour on computers, using many “virtual” ants. They can quickly find very good solutions for the travelling salesman problem.

One particularly useful property of ACS algorithms is that they can run continuously and adapt in real time to changes to the graph. These changes could be caused by car accidents and road closures on street networks, or by traffic spikes to web servers on computer networks.

The Travelling Salesman problem is

Finding a fast and exact algorithm would have serious implications in the field of computer science: it would mean that there are fast algorithms for *all* NP-hard problems. It would also render most of internet security useless, which relies on the fact that certain problems are believed to be very difficult for computers.

Finding a fast algorithm to solve the travelling salesman problem would also solve one of the most famous open problems in mathematics and computer science, the **P vs NP** problem. It is one of the seven

## Graph Theory in Everyday Life

Throughout this chapter we have seen many applications of graph theory, though some were somehow contrived. It turns out, however, that graphs are at the very heart of many objects and concepts in everyday life.

The internet, for example, is a vast, virtual graph. Every vertex is an individual webpage, and every edge means that there is a hyperlink between two pages. Note that links only go one way, so this graph is , and that this graph is *very, very, large*.

Some websites, like Wikipedia or Facebook, have lots of incoming links, while many smaller websites may have very few incoming links. This is the underlying concept which Google uses to sort search results.

Websites with more incoming links tend to be of higher quality and should be shown at the top of the search results. For example, when searching for “London”, official tourist information sites are shown before small shops in London, or blogs of people who live in London. This simple idea from Graph theory, the **Page Rank Algorithm**, made Google significantly better than other early search engines.

The internet is the largest network ever created by mankind. This image shows a very small proportion of all the computers and devices connected to the internet.

While websites and hyperlinks form a *virtual* graph, there is also the *physical* network of computers, servers, routers, phone lines and cables.

Every time you make a phone call or load a website, network operators have to find a way to connect sender and receiver, without exceeding the capacity of any individual cable or connection. Graph theory and probability make it possible to guarantee a reliable service, for example by finding diversions when a particular connection is busy.

Graphs also play an important role in transportation and navigation. All flight, train and subway networks form graphs, which can be used when creating efficient schedules. One of the most recognisable graphs is the London Underground map:

All roads and motorways also form a large network, which is used by navigation services like Google Maps when working out the shortest route between two given points.

In the future, **Intelligent Transportation Systems** will reduce congestion and accidents by routing cars more efficiently, using location data collected from smartphones and self-driving cars. This could save millions of hours lost on the road every year, significantly reduce pollution, and allow emergency services to travel faster.

This image shows the network of commercial airline flights across northern Europe.

There are countless other graphs in science, engineering or everyday life:

The links between atoms in **molecules** and crystal grids form a graph.

The **spread of diseases** and epidemics can be modelled using a network.

In Biology, the **evolutionary trees** that show the ancestry of species form a graph.

The different components of **electric circuits** and computer chips form a network.

The grammatical structure of **languages** can be modelled using graphs, for example to create translation algorithms.

Graphs also have many applications in **probability**, **game theory** and **financial mathematics**.

## Social Networks

Finally, let us think about one particularly good example of graphs which exist in everyday life: social media. Here, vertices represent

When we start drawing social media graphs, we can clearly see certain **clusters** of mutual friends, who may have gone to the same school or live in the same city. We can also determine people's **centrality**, which depends on how well-connected a vertex is, and which may be a measure of a person’s popularity in social media.

In 2014, Facebook had 1.4 billion active users and a total of more than 200 billion friendships. Half of all Facebook users have more than 200 friends, and since most of our friends have a similar number of friends, we could easily have tens of thousands of *friends of friends*.

An exciting question would now be: if you pick any two random Facebook users, how many “friendship edges” would you need to follow to get from one to the other? For example, the distance between friends is

Based on a study which Facebook conducted in 2016, you are, on average, connected to anyone else on Facebook through at most 3.57 other people: we say there are 3.57 **Degrees of separation**.

In other words, if you pick any one of the billions of Facebook users all around the world, they will have a friend of a friend who knows a friend of one of your friends. And this includes celebrities, politicians or royalty…

In 1929, when the Hungarian author

In 1967,

Today, every one of us is part of countless invisible graphs, which underly our social interactions, travel, internet and technology, science, and so much more.