+
×
÷
²
()
Solve 6 out of 8 questions correctly
ProgressTutorForumGlossary

# Graphs and Networks

Discover the mathematical principles that connect our world: from shaking hands to travel and navigation, colouring maps and social networks.

Remember to login to save your progress and get personalised content. This textbook works best on larger devices like tablets or laptops.

## 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 , connected by lines, called . In mathematics, all these networks are 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.

Integrated Circuits

Supply Chains

Friendships

Neural Connections

The Internet

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 . Most graphs have many cycles as subgraphs.

## 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 , and every handshake is . Suppose that, including yourself and the host, there are \${hnd} people present. Now it is easy to count the number of edges, and we find that there \${(hnd == 2 ? 'is ' : 'are ') + hnd * (hnd-1) / 2 + (hnd == 2 ? ' handshake' : ' handshakes')}.

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 at the party shakes hands with \${n-1} others. That makes \${n} × \${n-1} = \${n * (n-1)} handshakes in total.

\${ handshakeTable(n) }

Unfortunately this answer is not quite right: we have counted every handshake , once for each of the two people involved. Therefore, the correct number of handshakes for \${n} guests is \${n} × \${n-1}2 = \${n*(n-1)/2}.

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 \${comp} vertices is often abbreviated as K\${comp}.

We have just shown that a complete graph with n vertices has n × (n – 1)2 edges.

On a different day, you are invited to a speed dating event for \${m} boys and \${f} girls. There are many small tables and every boy spends 5 minutes with each of the girls. How many individual “dates” are there in total?

In this case, the corresponding graph consists of two separate sets of vertices. Every vertex is connected to all the vertices in set, but none of the vertices in set. Graphs which have this layout are called bipartite graphs.

The bipartite graph with two sets of size x and y is often written as Kx,y. It has edges, which means that in the above example there are \${m} × \${f} = \${m*f} dates.

## The Bridges of Königsberg

One of the first mathematicians to think about graphs and networks was Leonhard Euler. Euler was intrigued by an old problem regarding the town of Königsberg near the Baltic Sea. (Today, the city is called Kaliningrad and located in Russia.)

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:

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 and every bridge connecting two regions is represented by a corresponding .

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”.

Try drawing these graphs with one continuous stroke:

Interactive coming soon…

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 degree:

These graphs are possible:
These graphs are not possible:
Colour vertices by

Comparing these numbers for graphs which are possible and those which are not possible, it seems that a graph can be drawn if it . This condition can be explained if we look at just a single vertex in the graph:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

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.

K3 is planar.

K4 .

K5 .

The complete graph K5 is the smallest graph that is not planar. Any other graph that contains K5 as a subgraph in some way is also not planar. This includes K6, K7, and all larger complete graphs.

The graph in the three utilities puzzle is the bipartite graph K3,3. It turns out that any non-planar graph must contain a K5 or a K3,3 or a subdivision of these two graphs as a subgraph.

### Planarity

This is a planar graph, but the \${n} vertices have been scrambled up. Rearrange the vertices so that none of the edges overlap.

## Euler’s Formula

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

Vertices

Faces

Edges

11 Vertices + Faces

Vertices

Faces

Edges

15 Vertices + Faces

Vertices

Faces

Edges

25 Vertices + Faces

When comparing these numbers, you will notice that the number of edges is always than the number of faces plus the number of vertices. In other words, F + V = E + 1. This result is called Euler’s equation and is named after the same mathematician who solved the Königsberg Bridges problem.

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 proof that works for any graph…

 F V E 0 1 0

0 + 1  =  0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.
Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.
If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.
Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.
Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

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 polyhedra, three dimensional shapes with polygonal faces. If we think of polyhedra as made of elastic bands, we can imagine stretching them out until they become flat, planar graphs:

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 + .

Icosahedron
one of the 5 Platonic Solids
20 Faces, 12 Vertices and 30 Edges

Small Rhombicosidodecahedron
one of the 13 Archimedean Solids
62 Faces, 60 Vertices and 120 Edges

Football, or Truncated Icosahedron
32 Faces (12 black and 20 white),
60 Vertices and 90 Edges

## 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:

0

Note that states or countries which only share a corner are allowed to have the same colour.
Alaska and Hawaii are isolated from all of the other states and can have any colour.

0
0
0

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 , and countries which get connected by an edge:

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 Francis Guthrie had to colour a map of counties in England. He observed that four colours seemed to suffice for any map he tried, but he was not able to find a proof that worked for 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 Wolfgang Haken and Kenneth Appel used a computer to finally solve it. They reduced infinitely many possible maps to 1936 special cases, which were each checked by a computer taking over 1000 hours in total.

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.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

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.

This map on a torus requires seven colours.

## The Travelling Salesman Problem

Let us think, once more, about networks and maps. Imagine that a delivery service has to visit \${tsn} different cities to distribute parcels. We can think of these cities as the vertices in a graph. If all of the cities are connected by streets, this is a , so there are \${tsn} × (\${tsn} – 1)2 = \${tsn*(tsn-1)/2} edges in total.

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 \${tsn1} cities, every Hamiltonian cycle must also contain \${tsn1} cities. Now,

\${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 DNA.

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 \${tsn2} cities there are \${tsn2}! = \${factorial(tsn2)} possible paths. Once you have hundreds or thousands of vertices, trying all possible paths becomes impossible, even using powerful computers.

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 NP-hard, which means that it is very difficult to be solved by computers (at least for large numbers of cities).

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 Millennium Prize Problems, each carrying a \$1m prize.

## 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.

© LyonLabs, LLC and Barrett Lyon, 2014

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 and edges represent friendships, likes, subscriptions or followers.

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 , the distance between friends of friends is , and so on.

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…

Geographic visualisation of all Facebook friendships in 2010.

In 1929, when the Hungarian author Frigyes Karinthy first proposed the idea of “six degrees of Separation”, there was no internet or social media, but the world had already started to become more interconnected.

In 1967, Stanley Milgram conducted a first empirical experiment, where 296 participants living in Nebraska and Kansas were asked to deliver a letter to a particular person living in Boston, Massachusetts. They all had to choose a friend to send the letter to, who then picked another friend. At every step, the letter moved closer to Boston. Milgram found that there were, on average, only 5.2 intermediate friends – 5.2 degrees of separation.

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.

## Outstanding!

Chapter completed