Graph theory AI HL
A graph is a set of vertices joined by edges, and most questions start by finding the degree of each vertex. The degrees give the number of edges and decide whether a route can use every edge exactly once. Weights then lead to two tasks: the cheapest way to connect every vertex, which is a minimum spanning tree, and the shortest route along every edge, which is the Chinese postman problem. Problems are given in words or as a list of edges, so draw your own sketch first and use the calculator to total the weights.
Formulas at a glance
None of the results on this page is in the formula booklet, so learn them. They are short rules rather than formulas, and each follows from counting how many edges meet at a vertex.
Handshaking lemma, with E edges
Not in the bookletDirected graph: every edge leaves one vertex and enters another
Not in the bookletEdges in a tree, or in a spanning tree, with n vertices
Not in the bookletEulerian circuit in a connected graph
Not in the bookletEulerian trail in a connected graph
Not in the bookletChinese postman route length
Not in the bookletWhich method to use
Decide first whether the question is about the degrees of the vertices, about a route along the edges, or about connecting the vertices as cheaply as possible. Then write the edges as a list so that none is missed.
| The question has | Use | Notes |
|---|---|---|
| Vertex degrees, and the number of edges, or a check that the degrees are possible | Add the degrees and halve: | An odd total is impossible, and the number of odd-degree vertices is always even |
| A directed graph, and the in-degree or the out-degree of a vertex | Count the arrows into the vertex for the in-degree, and out of it for the out-degree | The total of the in-degrees and the total of the out-degrees both equal the number of edges |
| A question whether a route can use every edge exactly once | Count the odd-degree vertices: none gives a circuit, exactly two gives a trail | The graph must also be connected, and a trail starts at one odd vertex and ends at the other |
| A weighted graph, and the shortest route that uses every edge and returns to the start | Chinese postman: the total weight plus the least extra length that pairs up the odd vertices | With two odd vertices add the shortest path between them; with four, compare the three ways of pairing them |
| A weighted graph, and the cheapest way to connect every vertex | Kruskal's algorithm (cheapest edges first, skipping cycles) or Prim's algorithm (grow from one vertex) | Both give the same total weight, and the tree has one fewer edge than there are vertices |
| A tree or a spanning tree, and the number of edges is wanted | The number of vertices minus 1 | A tree is connected and has no cycle |
Section 1 of 3 AHL3.14
Graph theory basics
A graph is a set of vertices joined by edges, and the degree of a vertex is the number of edges that meet at it. The handshaking lemma states that the degrees add up to twice the number of edges, which gives the edge count and shows that the number of odd-degree vertices is always even. The main types are simple, complete, weighted and directed graphs.
Degree, and what it tells you
Handshaking lemma
Not in the formula booklet - it follows because every edge adds exactly 1 to the degree of each of its two endpoints. It also proves that any graph has an even number of odd-degree vertices.
Degree sequences
A proposed degree sequence can only belong to a real graph if it sums to an even number, because the sum is twice the number of edges.
Use the sum test first to rule out impossible sequences before trying to draw a graph.
Key terms
What is a simple graph?
A simple graph has no loops and no more than one edge between any pair of vertices. Degree sequence questions usually assume a simple graph.
e.g. A graph with two separate edges that both join and is not simple.
What is a complete graph?
In a complete graph every pair of vertices is joined by exactly one edge. With vertices, each vertex has degree , so the handshaking lemma gives edges.
e.g. A complete graph on vertices has edges.
What is a tree?
A tree is a connected graph with no cycles. A tree with vertices always has edges.
e.g. A tree with vertices has edges.
What are in-degree and out-degree?
In a directed graph, the in-degree of a vertex counts the edges pointing into it and the out-degree counts the edges pointing out of it. Each directed edge adds to one out-degree and to one in-degree.
e.g. A directed edge from to adds to the out-degree of and to the in-degree of .
Worked example, step by step
The question No calculator needed [6 marks]
A small social app records which accounts follow which. An arrow means that account follows account . The five accounts , , , and have these follows: , , , , , , and . Treat the accounts as vertices of a directed graph and each follow as a directed edge.
(a) Find the out-degree and the in-degree of each vertex.
(b) Find the number of edges, and show that the out-degrees and the in-degrees give the same total.
(c) Determine whether the graph is strongly connected.
Worked solution: worked example
Answer: (a) out-degrees ; in-degrees for to (b) edges (c) strongly connected
Step 1 - Count the arrows leaving each vertex.
Reading the list of follows, the out-degrees are A1 - Out-degrees
Why? The out-degree of a vertex is the number of edges that start at it. starts and , so its out-degree is 2.
Step 2 - Count the arrows entering each vertex.
The in-degrees are A1 - In-degrees
Why? The in-degree of a vertex is the number of edges that end at it. Listing the sources of the arrows into each vertex avoids missing one.
Step 3 - Find the number of edges and compare the totals.
The out-degrees add to , so there are edges. The in-degrees add to , the same total. M1 - Add the out-degrees (or the in-degrees) A1 - edges, with both totals equal
Why? Every directed edge leaves exactly one vertex and enters exactly one vertex, so each total equals the number of edges. A mismatch would show a counting slip.
Step 4 - Test for strong connectivity.
A strongly connected graph has a route from every vertex to every other vertex. The closed walk uses only the listed edges and visits all five vertices, so each vertex can be reached from each other vertex by following it round. The graph is strongly connected. M1 - Find a closed walk through all the vertices that follows the arrows A1 - Strongly connected
Why? Direction matters here. A closed walk through every vertex that follows the arrows gives a route from any vertex to any other, which is what strongly connected means.
A1 Out-degrees
A1 In-degrees
M1 Add the out-degrees (or the in-degrees)
A1 edges, with both totals equal
M1 Find a closed walk through all the vertices that follows the arrows
A1 Strongly connected
Now you try: enter your answers to be marked
These are real practice questions. Type your answer in each box and press Mark it. The worked solution and mark scheme appear straight away, and your first attempt is the one that counts. Use the keyboard for powers, roots and trig, and the working box for your notes.
Worked solution: practice question 1
Find the minimum total cost.
Worked solution: practice question 2
Your score so far: 0 out of 7 marks
Calculator steps: Enter a calculation on the home screen
Common mistakes
- Forgetting the factor of 2 in the handshaking lemma. The sum of degrees equals , not - each edge is counted once at each of its two endpoints, so halve the degree sum to get the number of edges.
- Trying to sketch a graph before checking the degree sum is even. Any proposed degree sequence with an odd total sum is impossible for a simple graph - check the handshaking lemma first and save yourself the wasted diagram.
Section 2 of 3 AHL3.16
Traversals and circuits
An Eulerian trail uses every edge of a graph exactly once, while a Hamiltonian path visits every vertex exactly once. Whether an Eulerian circuit or trail exists depends on the degrees of the vertices: all even for a circuit, exactly two odd for a trail. Hamiltonian routes have no equally simple degree test, so they are found by searching the graph.
Eulerian and Hamiltonian routes
Eulerian circuits
A closed route using every edge exactly once (an Eulerian circuit) exists only if every vertex has even degree. If exactly two vertices are odd, an Eulerian trail (not a closed circuit) exists between them.
Not in the formula booklet - existence conditionHamiltonian cycles
A Hamiltonian cycle visits every vertex exactly once and returns to the start - the opposite focus to an Eulerian circuit, which is about edges.
Not in the formula booklet - there's no simple degree test like the Eulerian one. The nearest-neighbour algorithm gives an achievable upper bound on the shortest such cycle, not a guarantee of the optimal one.
Key terms
What is the degree of a vertex?
The degree of a vertex is the number of edges that meet at it. Degrees decide whether a route using every edge exactly once can exist.
e.g. A vertex joined to three other vertices by one edge each has degree , which is odd.
What is the difference between a walk, a trail and a path?
A walk is any route along edges, a trail is a walk that never repeats an edge, and a path is a walk that never repeats a vertex.
e.g. In a triangle with vertices , , , the route is a path, but is only a walk because it uses edge twice.
What is a Hamiltonian cycle?
A Hamiltonian cycle visits every vertex exactly once and returns to the start. It is about vertices, whereas an Eulerian circuit is about edges.
e.g. In a square with vertices , , , joined in order, the route is a Hamiltonian cycle.
What does it mean for a graph to be connected?
A graph is connected if there is a path between every pair of vertices. A route cannot jump between separate pieces, so a graph in separate pieces that each contain edges has no single route using every edge.
e.g. Two triangles with no edge between them form a graph that is not connected, so no single route uses all edges.
Worked example, step by step
The question Calculator needed [6 marks]
A courier must travel along every one of eight roads that join six depots to , and finish at the depot where the route started. The roads and their lengths in kilometres are: 4, 5, 3, 6, 7, 2, 5 and 4.
(a) Find the degree of each depot, and explain why no route can use every road exactly once and return to its start.
(b) Find the length of the shortest route that uses every road at least once and returns to its start.
Worked solution: worked example
Answer: (a) odd degrees at , , , , so no Eulerian circuit (b) km
Step 1 - Find the degree of each depot.
Counting the roads at each depot gives The degrees add to , which agrees with the eight roads.
Why? The degree is the number of edges at a vertex, and the check against twice the number of edges catches a missing road.
Step 2 - Decide about an Eulerian circuit.
The depots , , and have odd degree. A circuit that uses every road exactly once needs every degree to be even, and a trail needs exactly two odd vertices, so neither exists. A1 - Odd vertices , , , R1 - An Eulerian circuit needs every degree even (and a trail needs exactly two odd vertices)
Why? Each time a route passes through a vertex it uses one road in and one road out, so a vertex with an odd degree cannot be passed through every time. Four odd vertices rule out a circuit and a trail.
Step 3 - Pair the odd depots.
Some roads must be repeated, joining the four odd depots in pairs. The three pairings, using the shortest connection in each pair, are For , the shortest route is . For , the routes and are both . M1 - Compare the three pairings of the odd vertices using shortest distances A1 - Least pairing km
Why? Repeating a road adds one to the degree at each end, which makes odd vertices even. The pairing with the least total length adds the least extra distance.
Step 4 - Add the least extra length to the total.
The total of all the roads is km. Adding the least pairing, km, gives M1 - Add the least pairing to the total weight of the roads A1 - km
Why? The shortest route travels every road once and repeats the two roads and of the best pairing. Enter the sums on the calculator to avoid an arithmetic slip.
A1 Odd vertices , , ,
R1 An Eulerian circuit needs every degree even (and a trail needs exactly two odd vertices)
M1 Compare the three pairings of the odd vertices using shortest distances
A1 Least pairing km
M1 Add the least pairing to the total weight of the roads
A1 km
Now you try: enter your answers to be marked
Worked solution: practice question 1
Worked solution: practice question 2
Find the minimum weight closed route that covers every edge at least once.
Worked solution: practice question 3
Your score so far: 0 out of 13 marks
Calculator steps: Enter a calculation on the home screen
Common mistakes
- Assuming any pair of odd-degree vertices gives a circuit. Exactly two odd vertices means an Eulerian trail exists between them - it does not close back into a circuit unless every vertex is even degree.
- Mixing up edge-based and vertex-based conditions. An Eulerian circuit is about using every edge once (tested by vertex degree); a Hamiltonian cycle is about visiting every vertex once. They test different things and have different existence tests.
- Treating nearest-neighbour as the optimal tour. The nearest-neighbour algorithm only produces an achievable upper bound for the travelling salesman problem - a shorter tour may still exist.
Section 3 of 3 AHL3.16
Minimum spanning tree
A minimum spanning tree of a weighted graph is a connected set of edges that joins every vertex, contains no cycle and has the smallest possible total weight. Kruskal's algorithm builds it by adding the lightest available edge that does not form a cycle, and Prim's algorithm grows it outward from a starting vertex. For a graph with vertices the tree always has edges.
Building a minimum spanning tree
Kruskal's vs Prim's
Kruskal's: sort all edges by weight, add the cheapest one at a time, skipping any that would create a cycle.
Prim's: start at one vertex and repeatedly add the cheapest edge connecting the growing tree to a new vertex.
Not in the formula booklet - these are algorithms you apply by hand, showing your working at each step. Both always reach the same minimum total weight.
Key terms
What is a spanning tree?
A spanning tree is a subgraph that is connected, contains every vertex of the graph and has no cycles. A minimum spanning tree is the spanning tree with the smallest total weight.
e.g. In a triangle with vertices , , and edges , , , the edges and form a spanning tree.
What is a cycle, and why must a tree avoid it?
A cycle is a closed path that starts and ends at the same vertex without repeating any other vertex. A tree has no cycles because the last edge of a cycle is unnecessary for connecting the vertices.
e.g. In the triangle above, the route is a cycle, so all three edges cannot be in the tree.
How does Kruskal's algorithm work?
List the edges in increasing order of weight, then add each edge in turn unless it would form a cycle. Stop when the tree has one fewer edge than the number of vertices.
e.g. With edges , , and , Kruskal's algorithm adds and , rejects because it forms a cycle, then adds , for a total weight of .
How does Prim's algorithm work?
Start at any vertex, then repeatedly add the lowest-weight edge that joins a vertex already in the tree to a vertex not yet in it. Unlike Kruskal's algorithm, the tree stays connected at every stage.
e.g. With edges , , and , starting at , Prim's algorithm adds , then , then , giving a total weight of .
Worked example, step by step
The question Calculator needed [6 marks]
A council wants to link six villages to with new footpaths of the least possible total length. The possible paths and their lengths in kilometres are: 7, 4, 6, 5, 4, 9, 3, 10 and 6.
(a) Use Kruskal's algorithm to find the minimum spanning tree, and state its total length.
(b) Use Prim's algorithm, starting at , and give the order in which the edges are added.
Worked solution: worked example
Answer: (a) , , , , , total km (b) , , , ,
Step 1 - List the edges in order of length.
Why? Kruskal's algorithm always considers the shortest remaining edge, so the edges are sorted first. Edges of equal length can be taken in either order.
Step 2 - Add edges, skipping any that make a cycle.
Add , and , which join separate vertices. Reject (5): and are already joined through , so it would make the cycle , , . Add , which joins the groups and . Add , which brings in . The tree now has edges for vertices, so it is complete. M1 - Add edges in order of length, rejecting any that makes a cycle R1 - is rejected because it would form the cycle , , A1 - Edges , , , ,
Why? An edge whose two ends are already connected would create a cycle, so it is rejected. A spanning tree on vertices has edges, which is the signal to stop.
Step 3 - Find the total length.
The tree is , , , , , and its total length is A1 - km
Why? Add the lengths of the chosen edges on the calculator. The total of the edges chosen does not depend on the order in which they were added.
Step 4 - Apply Prim's algorithm from .
From the shortest edge is (4). The tree is next joined by its shortest edge, (6), then (4) joins , then (3) joins , then (6) joins . The order is with total km. M1 - Start at and add the shortest edge from the tree to a new vertex each time A1 - Order , , , ,
Why? Prim's algorithm grows one connected tree, always adding the shortest edge from the tree to a vertex not yet in it. It gives the same total as Kruskal's algorithm, which checks the answer.
M1 Add edges in order of length, rejecting any that makes a cycle
R1 is rejected because it would form the cycle , ,
A1 Edges , , , ,
A1 km
M1 Start at and add the shortest edge from the tree to a new vertex each time
A1 Order , , , ,
Now you try: enter your answers to be marked
Find the total weight of the minimum spanning tree.
Worked solution: practice question 1
Explain whether AC should be added, and state what check Kruskal's performs.
Worked solution: practice question 2
Find the number of edges in any spanning tree of this graph.
Worked solution: practice question 3
Your score so far: 0 out of 6 marks
Calculator steps: Enter a calculation on the home screen
Common mistakes
- Confusing a minimum spanning tree with a shortest path. A minimum spanning tree minimises the total cost to connect every vertex - it does not give the shortest route between two particular vertices, which is a different problem.
- Adding an edge in Kruskal's algorithm without checking for a cycle. Sorting by weight is only half the method - each candidate edge must also be rejected if both its endpoints are already connected through edges you've kept.
- Treating the MST as if it must visit every vertex and return to the start. That's the travelling salesman problem, a different task. A spanning tree is not a cycle, and it has no requirement to close back on itself.
Using your GDC
The exact key presses for the TI-84 Plus CE, Casio fx-CG50, Casio fx-CG100 and TI-Nspire CX, with what the screen shows. Pick your calculator.
Enter a calculation on the home screen
Used in: Graph theory basics, Traversals and circuits, Minimum spanning tree
How to enter a calculation on a TI-84 Plus CE
Type a calculation and press enter | |
Go to the home screen: press 2nd mode (QUIT) from any menu or app. Press clear if the entry line is not empty. |
|
Type the calculation as you would write it, then press enter. For press 3 ( 2 . 4 ) x² − 5 × 1 . 8 enter. The calculator understands a number next to a bracket as a multiplication, so × is not needed in . If a fraction, square root or power template is on the screen, press ▶ to move out of it before you carry on typing. |
3(2.4)²-5*1.8 8.28 |
Use the last answer in the next calculation | |
To increase the answer by 15%, press × 1 . 1 5 enter on a blank line. The calculator puts Ans, the last answer, in front of the operator for you. You can also type Ans yourself, anywhere in a calculation: press 2nd (−) (ANS), for example 2nd (−) (ANS) × 1 . 1 5 enter. , which is to 3 significant figures. |
Ans*1.15 9.522 |
To use an earlier entry or answer, press ▲ to move up through the history, then enter to paste the highlighted one on the entry line. Press 2nd enter (ENTRY) to bring back your last entry and change it. |
|
Ans always holds the last answer that was worked out, so if you do a different calculation in between, Ans changes. Type a number you need later, or keep it on the screen, rather than relying on Ans for many steps.
The full guide: Enter a calculation on the home screen
See the full list of GDC guides for every calculator task.
Syllabus content covered
| Code | Syllabus content |
|---|---|
| AHL3.14 | Graphs: vertices, edges, adjacent vertices, adjacent edges, degree of a vertex. Simple, complete, weighted and directed graphs (with in-degree and out-degree). Subgraphs and trees. Knowledge of the terms connected and strongly connected. Students should be able to represent real-world structures - circuits, maps, etc - as graphs. |
| AHL3.16 | Walks, trails, paths, circuits and cycles. Eulerian trails and circuits, and how to determine whether one exists. Hamiltonian paths and cycles. Minimum spanning tree algorithms (Kruskal's and Prim's). The Chinese postman problem for a graph with up to four odd vertices. The travelling salesman problem, with the nearest neighbour algorithm for an upper bound and the deleted vertex algorithm for a lower bound. |
Official IB source: Mathematics: applications and interpretation subject brief (PDF, ibo.org).
Quick questions
What is the handshaking lemma?
The sum of all vertex degrees in a graph equals twice the number of edges, since every edge contributes 1 to the degree of each of its two endpoints.
When does a graph have an Eulerian circuit?
A connected graph has an Eulerian circuit - a closed route using every edge exactly once - if and only if every vertex has even degree.
How many edges does a minimum spanning tree have?
A spanning tree on vertices always has exactly edges - enough to connect every vertex with no cycles, and no more.
What does strongly connected mean for a directed graph?
A directed graph is strongly connected if, following the arrows, there is a route from every vertex to every other vertex. A graph can be connected without being strongly connected, because the arrows may only allow travel one way between two vertices.
What is the difference between an Eulerian trail and an Eulerian circuit?
Both use every edge exactly once. A circuit returns to its starting vertex and needs all vertices to have even degree; a trail does not return to the start and needs exactly two odd-degree vertices, which become the endpoints.
Do Kruskal's and Prim's algorithms always give the same minimum spanning tree?
They always produce a tree of the same minimum total weight, but if two or more edges tie in weight the two methods can pick a different set of edges to reach it.
Why must the number of odd-degree vertices be even?
The degrees add up to , which is even. Even degrees contribute an even total, so the odd degrees must also add to an even number, which needs an even count of odd-degree vertices.
Does a Hamiltonian cycle have to use every edge?
No. It must visit every vertex exactly once, and any edges left over are simply not used. For example, a complete graph on vertices has edges, but a Hamiltonian cycle in it uses only .
How is a minimum spanning tree different from a shortest path?
A minimum spanning tree joins all vertices with the least total weight, while a shortest path joins two chosen vertices with the least weight along the route. With , and , the minimum spanning tree uses and with weight , but the shortest path from to is the single edge of weight .
Does an even degree sum guarantee that a simple graph exists?
No. For example, has sum , but on vertices each vertex of degree must be joined to every other vertex, which would give the last vertex degree , not .
Ready to practise properly?
Practice questions on every section, marked instantly like the real exam.