3.14 Graph theory

Learning objectives

• Represent real-world structures, such as maps, transport networks, molecules and circuits, as graphs, weighted or unweighted.

• Identify vertices, edges, adjacent vertices and adjacent edges in a graph.

• Find the degree of each vertex, counting a loop twice, and use the fact that the sum of the degrees is twice the number of edges.

• Determine whether a graph is simple or complete, and calculate the number of edges in a complete graph.

• Draw a weighted graph from a table of distances, costs or times.

• Find the in-degree and out-degree of each vertex of a directed graph.

• Determine whether a graph is connected, and whether a directed graph is strongly connected, with a reason.

• Identify subgraphs and trees, and use the fact that a tree with $n$ vertices has $n - 1$ edges.

Introduction

A road map, a metro map, a family tree, a list of who follows whom online and the structural formula of a molecule all record the same kind of information: a set of objects and the connections between them. Graph theory studies structures of this kind in their simplest form, as points joined by lines, and ignores everything else. Once a real situation has been reduced to points and lines, the same mathematics answers questions about very different systems: whether every station can be reached from every other, how many connections a hub has, or whether a network has any redundant links.

The subject began with a puzzle about the seven bridges of the Prussian city of Königsberg (now Kaliningrad), which Leonhard Euler analysed in 1736. Today graph theory underpins route planning, internet search, electricity grids, chemistry and the study of social networks. It also supplies the language for subtopic 3.15, Adjacency matrices, and subtopic 3.16, Tree and cycle algorithms.

YouTube

Graphs, vertices and edges

From a map to a graph

Königsberg was built on both banks of the River Pregel and on two areas of land in the river: the island of Kneiphof and a piece of land to the east between two branches of the river. Seven bridges joined these four land masses. Euler's own sketch of the city, published with his solution, labels the island A, the two river banks B and C, and the eastern land D, with the bridges lettered a to g.

Euler realised that the size and shape of each land mass made no difference to any question about crossing bridges. Only the list of land masses and the list of bridges joining them mattered. Replacing each land mass by a point and each bridge by a line joining two points gives a picture, called a graph, that contains exactly the information needed and nothing else.

The central object of the subject is the graph itself. A graph needs two ingredients, a collection of objects and a list of which pairs of them are connected, and it records nothing else.

The points and lines of a graph have their own names. In a real situation the vertices might be towns, stations, people, atoms or web pages, and the edges might be roads, rail links, friendships, chemical bonds or hyperlinks.

Each bridge of Königsberg becomes a line between the two land masses it joins. Two bridges, a and b, join A to B, and two more, c and d, join A to C, so the graph has two separate lines between each of those pairs of vertices. The figure of the Königsberg graph shows all seven bridges as edges.

The word "vertex" also appears in subtopic 3.6, where a vertex of a Voronoi diagram is a point where cell boundaries meet, and in subtopic 2.5 for the turning point of a parabola. These are different ideas that happen to share a name; in graph theory a vertex is simply one of the objects being connected.

Only the connections matter

The only information in a graph is which vertices are joined. The position of a vertex on the page, the length of a line and whether it is straight or curved carry no meaning. Two drawings that look completely different are the same graph if they have the same vertices joined by the same edges.

Two consequences follow. First, a point where two drawn edges cross is not a vertex unless it is marked as one: in a road network, a bridge that carries one road over another is not a junction. Second, a graph drawn from a real map does not need to look like the map. Redrawing it with the vertices spread out often makes it easier to read.

Adjacent vertices and adjacent edges

Two vertices joined directly by an edge are neighbours in the graph. In the Königsberg graph, A and D are joined by bridge e, so they are adjacent. B and C are not joined directly by any bridge, so they are not adjacent, even though a person could walk from B to C by crossing two bridges.

Edges can be adjacent too. Two edges are adjacent when they meet at a vertex, so that one can be followed directly after the other. Bridges a and f are adjacent because both end at B; bridges a and g are not adjacent, because they have no vertex in common.

Loops and multiple edges

Two special kinds of edge appear in some graphs. An edge may start and finish at the same vertex: a road that leaves a village and returns to it without passing anywhere else, or a web page with a link to itself. Two vertices may also be joined by more than one edge, as with the pairs of bridges in Königsberg or two different rail lines that both run between the same two stations.

The graph in the figure of a graph with a loop and multiple edges has six vertices. It has two edges joining R and T and a loop at T, and the vertex U has no edges at all; a vertex like U, joined to nothing, is called an isolated vertex.

Degree of a vertex

Counting the edges at a vertex

The most useful single number about a vertex is how many edges meet there. At a road junction it is the number of roads leading out; at an atom in a molecule it is the number of bonds; in a social network it is the number of friends a person has.

A loop adds 2 to the degree because both of its ends are at the same vertex. The reason becomes clear by drawing a small circle around the vertex: an ordinary edge crosses the circle once, but a loop leaves through the circle and comes back through it, crossing twice. Counting ends instead of edges keeps the rule the same for every kind of edge.

In the graph with vertices P to U, vertex T has two edges to R and one loop, so

Vertex R meets QR, RS, PR and the two edges to T, so $\deg(R) = 5$. The isolated vertex U has degree 0.

Odd and even vertices

Whether a degree is odd or even turns out to matter more than its actual value. Euler's whole argument about Königsberg rests on it, and it decides in subtopic 3.16 whether a route can use every edge of a graph exactly once.

An isolated vertex has degree 0, and 0 is an even number, so an isolated vertex counts as even.

The sum of the degrees

Adding up the degrees of all the vertices of a graph gives a total that is linked directly to the number of edges. Every edge has two ends. When the degrees are added, each end is counted once, at the vertex where it lies, so every edge is counted exactly twice: once at each end, or twice at the same vertex if it is a loop.

For the Königsberg graph, $5 + 3 + 3 + 3 = 14 = 2 \times 7$, matching the seven bridges. For the graph with vertices P to U, $3 + 2 + 5 + 2 + 4 + 0 = 16 = 2 \times 8$

Two facts follow directly from this result.

• The sum of the degrees of any graph is even, because it is twice a whole number.

• The number of odd vertices in any graph is even. The even vertices contribute an even amount to the total, so the odd vertices must also add up to an even number, and a sum of odd numbers is even only when there is an even number of them.

The second fact means that a graph can have 0, 2, 4, 6, … odd vertices, but never 1, 3 or 5. The Königsberg graph has four; the graph with vertices P to U has two (P and R).

Simple graphs and complete graphs

Simple graphs

Many networks have at most one direct link between any two places and never link a place to itself. A list of which pairs of countries share a land border, or which pairs of people are friends, has this property. A graph like this is called simple.

Whether a graph should be drawn as simple depends on the question being asked. For "Which land masses can be reached directly from which?" a single edge between A and B is enough, giving a simple graph. For "How many ways are there to cross from A to B?" or "Can every bridge be crossed exactly once?" both bridges matter and both edges must be drawn.

Complete graphs

At the other extreme from a sparse network is one in which every pair of vertices is directly linked: a round-robin tournament in which every team plays every other team once, or a group of people in which everyone knows everyone else.

The number of edges of a complete graph

The edge counts 1, 3, 6, 10 follow a pattern that can be justified in two ways.

By degrees. In $K_n$ each vertex is joined to the other $n - 1$ vertices, so every vertex has degree $n - 1$. The sum of the degrees is $n(n - 1)$

By counting pairs. Each edge corresponds to one pair of vertices. Choosing the first vertex of a pair gives $n$ options and the second gives $n - 1$, but this counts every pair twice (AB and BA), so the number of pairs is $\frac{n(n-1)}{2}$.

A complete graph has the most edges any simple graph on $n$ vertices can have, because a simple graph cannot join a pair of vertices more than once. So a simple graph with $n$ vertices has at most $\frac{n(n-1)}{2}$ edges. The number of edges grows roughly like $\frac{n^2}{2}$

Weighted graphs

In many problems a connection is not just present or absent: it has a size. A road has a length, a flight has a cost, a cable takes a certain time to install. Writing these numbers on the edges turns a graph into a weighted graph, the model used for finding shortest routes and cheapest networks in subtopic 3.16.

A weighted graph is often given as a table instead of a drawing. Each row and column is a vertex, each entry is the weight of the edge joining them, and a blank (or a dash) means that there is no direct edge. Subtopic 3.15 calls this a weighted adjacency table.

Road distances in kilometres between five villages (hypothetical). A blank cell means no direct road.

To draw the graph, mark the five vertices, then go along each row and draw an edge for every entry, writing its weight on it. Because the table is symmetric (the entry for B to C equals the entry for C to B), each road appears twice in the table but is drawn only once. The resulting weighted graph has seven edges.

Weights do not have to match the drawing. The edge BC, of weight 5, is drawn longer than the edge AB, of weight 7, which is acceptable because only the number on an edge carries information. Weights also do not have to behave like straight-line distances. In this network each direct road happens to be the shortest way between its two villages, but in a real road network a winding direct road can be longer than a route through another village, and a weight that is a cost or a time need not follow any geometric rule at all.

Directed graphs

Edges with a direction

Some connections only work one way. A one-way street can be driven along in only one direction, a flight route may run from one city to another without a return flight, and on a social media platform one account can follow another without being followed back. A graph whose edges have directions models these situations.

A two-way connection in a directed graph is shown by two edges, one in each direction. The figure of follows between five accounts on a social media platform (hypothetical) has an edge from A to B and another from B to A, which means that A and B follow each other.

In-degree and out-degree

In a directed graph the edges at a vertex are of two kinds, those arriving and those leaving, so each vertex has two degrees.

The out-degree counts the other kind of edge, the ones leaving the vertex. In the follower graph it is the number of accounts that a person follows.

Every directed edge has exactly one start and exactly one end. Adding up all the out-degrees therefore counts each edge once, and so does adding up all the in-degrees.

This replaces the "twice the number of edges" rule for undirected graphs, and it gives a quick check on any table of in-degrees and out-degrees. The total degree of a vertex, ignoring directions, is its in-degree plus its out-degree.

Connected and strongly connected graphs

Connected graphs

A transport network is only useful if a traveller can get from any station to any other, perhaps by changing lines several times. The same property matters for an electricity grid, a computer network or a water supply: every part must be linked to every other part, directly or indirectly.

The upper half of the figure comparing connected and disconnected graphs shows two graphs, each with five vertices and four edges. The first is connected. The second is not, because no sequence of edges leads from the triangle to the separate pair of vertices.

Strongly connected directed graphs

For a directed graph, the arrows must be obeyed. A network of one-way streets can be in one piece on the map and still trap a driver: if a street leads into a district and every street out of the district runs the wrong way, the driver cannot leave. Connectivity that respects the directions has its own name.

In the lower left digraph of the figure, the edges P → Q → R → S → P form a closed route through all four vertices, so any vertex can reach any other by going round it. The graph is strongly connected. In the lower right digraph, S has out-degree 0, so nothing can be reached from S; this graph is connected if directions are ignored, but it is not strongly connected.

Two quick tests help in practice.

• A reason it fails. If any vertex has out-degree 0, nothing can be reached from it; if any vertex has in-degree 0, it cannot be reached from anywhere. Either one shows the graph is not strongly connected.

• A reason it holds. If a single closed route following the arrows passes through every vertex, the graph is strongly connected, because any vertex can reach any other by going round that route.

Neither test settles every case: a graph can have every in-degree and out-degree at least 1 and still not be strongly connected. When in doubt, check from one vertex which vertices can be reached, then check that every vertex can get back to it.

Subgraphs and trees

Subgraphs

A large network often contains smaller networks worth studying on their own: the stations of one metro line, the roads in one district, or the cables actually installed out of all those that could have been. Each of these is a part of the original graph.

When a vertex is removed, every edge at that vertex must be removed too, because an edge cannot have a missing end. Removing edges alone keeps all the vertices. The figure of a graph G with a subgraph H and a tree T shows both: H drops the vertex F (and with it the edges FA, FE and FC) and some other edges, while T keeps every vertex but only five edges.

Trees

Some networks connect everything without any redundancy. A family tree, a folder structure on a computer, the branching of a river system and the chain of carbon atoms in butane all link every part to every other part in exactly one way. Graphs of this kind are called trees.

The idea of a cycle is developed fully in subtopic 3.16. For trees it is enough to see that a cycle provides two different ways between some pair of vertices, which a tree never has. Graph G in the figure is not a tree, because it contains cycles such as A–B–C–D–A. Subgraph H is also not a tree: it contains the cycle A–B–C–D–A. Tree T has no cycles and is connected.

A tree with n vertices has n − 1 edges

Every tree with $n$ vertices has exactly $n - 1$ edges. One way to justify this is to build the tree one vertex at a time. Start with a single vertex and no edges. Each new vertex must be attached by exactly one edge: with no edge it would not be connected, and with two edges to vertices already in the tree it would create a cycle, since those two vertices were already linked. So each of the remaining $n - 1$ vertices brings exactly one edge, giving $n - 1$

The same argument gives the least number of edges a connected graph can have. A connected graph on $n$ vertices needs at least $n - 1$ edges, and with exactly $n - 1$ edges it is a tree. Combining this with the complete graph:

The lower limit is reached by a tree and the upper limit by $K_n$. A tree that is a subgraph of a graph and includes all of its vertices, like T inside G, is called a spanning tree; finding the cheapest one is the minimum spanning tree problem of subtopic 3.16.

Representing real structures as graphs

Deciding what the vertices and edges are

Turning a real situation into a graph is an act of modelling: deciding what to keep and what to ignore. The same street map can give different graphs depending on the question.

1. Choose the vertices. These are the places or objects between which connections are made: junctions, towns, buildings, people, components.

2. Choose the edges. Each direct connection becomes an edge. Decide whether repeated connections (two bridges, two cables) must be drawn separately, and whether a loop has any meaning.

3. Decide on direction. If connections work one way only (one-way streets, followers, flights without a return), use a directed graph.

4. Decide on weights. If the question involves distance, cost or time, write the weight on each edge.

5. Check the result. Count edges and degrees against the description: the degree sum must be twice the number of edges (or the in-degree and out-degree sums must equal it).

For an electrical circuit, the junctions where wires meet are the vertices and the wires or components between junctions are the edges; two components connected in parallel between the same junctions become multiple edges. For a map of countries, each country is a vertex and two countries are joined when they share a border, giving a simple graph.

Case study: central London's Underground interchanges

The London Underground has 11 lines, about 400 km (250 miles) of track and 272 stations. Its map, first designed by Harry Beck in 1931 and introduced in 1933, is a familiar example of a graph-like map. Beck saw that passengers underground need to know which stations are connected and where to change, not where the stations lie on the surface. His map places stations to make the connections clear and draws lines only horizontally, vertically or at 45°, so distances on it are not to scale.

The figure of central London interchanges shows the subgraph of the Underground made up of nine central stations, with one edge for each pair of stations that are next to each other on an Underground line. The table lists the edges by line.

Source: Wikipedia, station articles ("Adjacent stations"), October 2026; network size from "London Underground", 2026.

Degrees. Counting one edge per line, Oxford Circus has degree 4 (to Bond Street, Tottenham Court Road, Green Park and Piccadilly Circus), as do Green Park, Piccadilly Circus, Charing Cross and Embankment. Bond Street and Tottenham Court Road have degree 2, and Leicester Square and Westminster have degree 3. The degree sum is

matching the 15 edges in the table. There are two odd vertices, Leicester Square and Westminster, an even number as the degree sum requires.

Simple or not. With one edge per line the graph has multiple edges, so it is not simple. If the question is only "which stations are next to each other?", each double edge becomes one edge and the graph is simple with 13 edges. A degree of 4 at Oxford Circus means four neighbouring stations, and it is the same in both versions; at Embankment the degree falls from 4 to 2.

Connected, but far from complete. Every station can be reached from every other, so the graph is connected. A complete graph on 9 vertices would need far more edges than the simple version's 13:

Only 13 of the 36 pairs of stations are next to each other on a line, so a journey between most pairs passes through at least one intermediate station.

What the model leaves out. The graph ignores distances, journey times, the time taken to change lines inside a station, the many other stations of each line and the Elizabeth line, which is not part of the Underground. Adding journey times as weights would turn it into a weighted graph suitable for route planning. The model also treats each station as a single point, which is reasonable for planning journeys but not for planning the walk between platforms.

YouTube

Exam focus

Graph theory vocabulary is examined on HL Papers 1, 2 and 3, usually in the first parts of a longer network question. Typical parts ask you to draw a graph from a map, description or table (often with weights or directions), write down the degree of each vertex, state whether a graph is simple, complete, connected, strongly connected or a tree, and write down a route through every vertex. These openings carry 1–3 marks each and lead into adjacency matrices (subtopic 3.15) or algorithms such as Kruskal's, Prim's and the Chinese postman algorithm (subtopic 3.16). There are no formulas for graph theory in the formula booklet, so the definitions and the facts $\sum \deg = 2 \times \text{edges}$, $K_n$

For "state whether" and "determine whether" questions about connectivity or trees, the conclusion earns its mark only with a valid reason. Name a specific feature: a cycle, a vertex with out-degree 0, the count of edges compared with $n - 1$, or a missing edge for "complete".

Graph vocabulary is also the language of the reasons asked for later in a long question. A part on the Chinese postman problem needs the odd vertices, a part on a minimum spanning tree needs $n - 1$ edges, and a part on PageRank needs the graph to be strongly connected, so a careful table of degrees at the start often earns marks several parts later.

Practice questions

1. A graph has vertices with degrees 6, 4, 4, 3, 3, 2 and 2. Find the number of edges. [2]

2. Explain why it is impossible for 11 students in a class each to have exactly 3 friends within the class (friendship being mutual). [2]

3. Find the number of edges in $K_{15}$. [1]

4. A simple graph has 9 vertices and 30 edges. Find how many more edges are needed to make it complete. [2]

5. A connected graph has 20 vertices and 19 edges. State what type of graph it is, and write down the number of edges that would have to be added to create exactly one cycle. [2]

6. A directed graph has edges U → V, V → W, W → U, W → X, X → Y and Y → W. (a) Write down the in-degree and out-degree of W. (b) Determine, with a reason, whether the graph is strongly connected. [4]

7. A network of streets in a town centre is to be modelled as a graph. Two parallel streets both join junction J to junction K, and a looped street leaves junction M, circles a square and returns to M without meeting any other junction. (a) Explain how each feature appears in the graph. (b) State whether the graph is simple. [3]

8. The degrees of the vertices of a simple graph are 1, 1, 2, 2, 2 and 4. Show that the graph is not a tree. [2]

9. In a hockey league each of $n$

Summary

• A graph is a set of vertices joined by edges; only which vertices are joined matters, not positions, lengths or crossings in the drawing.

• Adjacent vertices are joined by an edge; adjacent edges share a vertex. A loop joins a vertex to itself; multiple edges join the same pair of vertices.

• The degree of a vertex counts edge-ends there (a loop counts 2). The sum of the degrees is twice the number of edges, so the number of odd vertices is always even.

• A simple graph has no loops or multiple edges. The complete graph $K_n$ joins every pair of its $n$ vertices and has $\frac{n(n-1)}{2}$

Self-check

• To do:

  I can draw a graph from a map, description or table, including multiple edges and loops where the context needs them.

• To do:

  I can explain why the positions and lengths of edges in a drawing carry no information.

• To do:

  I can list the vertices adjacent to a given vertex and the edges adjacent to a given edge.

• To do:

  I can find the degree of every vertex, counting a loop as 2.

• To do:

  I can use the degree sum to find a number of edges or to show that a graph cannot exist.

• To do:

  I can explain why every graph has an even number of odd vertices.

• To do:

  I can decide whether a graph is simple and whether it is complete.

• To do:

  I can find the number of edges of $K_n$ and solve for $n$