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

∑deg⁡(v)=2E\sum\deg(v)=2E

Not in the booklet

Directed graph: every edge leaves one vertex and enters another

∑out-degrees=∑in-degrees=E\sum\text{out-degrees}=\sum\text{in-degrees}=E

Not in the booklet

Edges in a tree, or in a spanning tree, with n vertices

n−1n-1

Not in the booklet

Eulerian circuit in a connected graph

every vertex has even degree\text{every vertex has even degree}

Not in the booklet

Eulerian trail in a connected graph

exactly two vertices have odd degree\text{exactly two vertices have odd degree}

Not in the booklet

Chinese postman route length

total weight+least extra weight that pairs the odd vertices\text{total weight}+\text{least extra weight that pairs the odd vertices}

Not in the booklet

Which 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 hasUseNotes
Vertex degrees, and the number of edges, or a check that the degrees are possibleAdd the degrees and halve: ∑deg⁡(v)=2E\sum\deg(v)=2EAn 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 vertexCount the arrows into the vertex for the in-degree, and out of it for the out-degreeThe 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 onceCount the odd-degree vertices: none gives a circuit, exactly two gives a trailThe 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 startChinese postman: the total weight plus the least extra length that pairs up the odd verticesWith 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 vertexKruskal'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 wantedThe number of vertices minus 1A 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

∑deg⁡(v)=2E\displaystyle\sum \deg(v) = 2E

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 AA and BB is not simple.

What is a complete graph?

In a complete graph every pair of vertices is joined by exactly one edge. With nn vertices, each vertex has degree n−1n-1, so the handshaking lemma gives n(n−1)2\dfrac{n(n-1)}{2} edges.

e.g. A complete graph on 55 vertices has 5×42=10\dfrac{5\times4}{2}=10 edges.

What is a tree?

A tree is a connected graph with no cycles. A tree with nn vertices always has n−1n-1 edges.

e.g. A tree with 1111 vertices has 1010 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 11 to one out-degree and 11 to one in-degree.

e.g. A directed edge from AA to BB adds 11 to the out-degree of AA and 11 to the in-degree of BB.

Worked example, step by step

The question No calculator needed [6 marks]

A small social app records which accounts follow which. An arrow X→YX\to Y means that account XX follows account YY. The five accounts AA, BB, CC, DD and EE have these follows: A→BA\to B, A→CA\to C, B→CB\to C, B→EB\to E, C→AC\to A, C→DC\to D, D→ED\to E and E→CE\to C. 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 2,2,2,1,12,2,2,1,1; in-degrees 1,1,3,1,21,1,3,1,2 for AA to EE (b) 88 edges (c) strongly connected

Step 1 - Count the arrows leaving each vertex.

Reading the list of follows, the out-degrees are A:2,B:2,C:2,D:1,E:1.A:2,\quad B:2,\quad C:2,\quad D:1,\quad E:1. A1 - Out-degrees 2,2,2,1,12,2,2,1,1

Why? The out-degree of a vertex is the number of edges that start at it. AA starts A→BA\to B and A→CA\to C, so its out-degree is 2.

Step 2 - Count the arrows entering each vertex.

The in-degrees are A:1 (from C),B:1 (from A),C:3 (from A,B,E),D:1 (from C),E:2 (from B,D).A:1\ (\text{from }C),\quad B:1\ (\text{from }A),\quad C:3\ (\text{from }A,B,E),\quad D:1\ (\text{from }C),\quad E:2\ (\text{from }B,D). A1 - In-degrees 1,1,3,1,21,1,3,1,2

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 2+2+2+1+1=82+2+2+1+1=8, so there are 88 edges. The in-degrees add to 1+1+3+1+2=81+1+3+1+2=8, the same total. M1 - Add the out-degrees (or the in-degrees) A1 - 88 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 A→B→E→C→D→E→C→AA\to B\to E\to C\to D\to E\to C\to A 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.

Marks (6):
A1 Out-degrees 2,2,2,1,12,2,2,1,1
A1 In-degrees 1,1,3,1,21,1,3,1,2
M1 Add the out-degrees (or the in-degrees)
A1 88 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.

1
Easy
Calculator
[3 marks]
A graph has 6 vertices with degrees 3,3,4,2,2,2.3, 3, 4, 2, 2, 2.
(a) State the handshaking lemma.
[1]
(b) Find the number of edges.
[2]
Fractions & powers
Other

Worked solution: practice question 1

2
Medium
Calculator
[4 marks]
A company connects 5 offices. The minimum spanning tree has edge weights 8, 6, 9, 7 (km). Cable costs $1200 per km.

Find the minimum total cost.
[4]
Fractions & powers
Other

Worked solution: practice question 2

Your score so far: 0 out of 7 marks

Common mistakes

  • Forgetting the factor of 2 in the handshaking lemma. The sum of degrees equals 2E2E, not EE - 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.

Try some questions on graph theory basics

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 condition

Hamiltonian 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 33, 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 AA, BB, CC, the route A→B→CA\to B\to C is a path, but A→B→C→A→BA\to B\to C\to A\to B is only a walk because it uses edge ABAB 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 AA, BB, CC, DD joined in order, the route A→B→C→D→AA\to B\to C\to D\to A 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 66 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 AA to FF, and finish at the depot where the route started. The roads and their lengths in kilometres are: ABAB 4, ACAC 5, BCBC 3, BDBD 6, CECE 7, DEDE 2, DFDF 5 and EFEF 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 BB, CC, DD, EE, so no Eulerian circuit (b) 4141 km

Step 1 - Find the degree of each depot.

Counting the roads at each depot gives A:2,B:3,C:3,D:3,E:3,F:2.A:2,\quad B:3,\quad C:3,\quad D:3,\quad E:3,\quad F:2. The degrees add to 16=2×816=2\times8, 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 BB, CC, DD and EE 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 BB, CC, DD, EE 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 BC+DE=3+2=5,BD+CE=6+7=13,BE+CD=8+9=17.BC+DE=3+2=5,\qquad BD+CE=6+7=13,\qquad BE+CD=8+9=17. For BEBE, the shortest route is B→D→E=6+2=8B\to D\to E=6+2=8. For CDCD, the routes C→B→DC\to B\to D and C→E→DC\to E\to D are both 99. M1 - Compare the three pairings of the odd vertices using shortest distances A1 - Least pairing 55 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 4+5+3+6+7+2+5+4=364+5+3+6+7+2+5+4=36 km. Adding the least pairing, 55 km, gives 36+5=41 km.36+5=41\text{ km}. M1 - Add the least pairing to the total weight of the roads A1 - 4141 km

Why? The shortest route travels every road once and repeats the two roads BCBC and DEDE of the best pairing. Enter the sums on the calculator to avoid an arithmetic slip.

Marks (6):
A1 Odd vertices BB, CC, DD, EE
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 55 km
M1 Add the least pairing to the total weight of the roads
A1 4141 km

Now you try: enter your answers to be marked

1
Easy
No calc
[3 marks]
A graph G has an Eulerian circuit. A new edge is added between two distinct vertices that are already in G.
(a) What happens to the degrees of those two vertices?
[2]
(b) Does the modified graph necessarily still have an Eulerian circuit?
[1]
Fractions & powers
Other

Worked solution: practice question 1

2
Medium
No calc
[5 marks]
Consider a connected graph.
(a) State the condition for a connected graph to have an Eulerian circuit.
[2]
(b) A graph has vertex degrees 2,2,3,3,4.2, 2, 3, 3, 4. Determine whether it has an Eulerian circuit, an Eulerian trail, or neither.
[3]
Fractions & powers
Other

Worked solution: practice question 2

3
Hard
No calc
[5 marks]
A graph has total edge weight 60 and four odd-degree vertices A, B, C, D. The shortest distances between them are: AB=3, CD=5, AC=4, BD=6, AD=7, BC=2.

Find the minimum weight closed route that covers every edge at least once.
[5]
Fractions & powers
Other

Worked solution: practice question 3

Your score so far: 0 out of 13 marks

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.

Try some questions on traversals and circuits

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 nn vertices the tree always has n−1n-1 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 AA, BB, CC and edges ABAB, BCBC, CACA, the edges ABAB and BCBC 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 A→B→C→AA\to B\to C\to A 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 AB=2AB=2, BC=3BC=3, AC=4AC=4 and CD=5CD=5, Kruskal's algorithm adds ABAB and BCBC, rejects ACAC because it forms a cycle, then adds CDCD, for a total weight of 1010.

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 AB=2AB=2, BC=3BC=3, AC=4AC=4 and CD=5CD=5, starting at AA, Prim's algorithm adds ABAB, then BCBC, then CDCD, giving a total weight of 1010.

Worked example, step by step

The question Calculator needed [6 marks]

A council wants to link six villages AA to FF with new footpaths of the least possible total length. The possible paths and their lengths in kilometres are: ABAB 7, ACAC 4, BCBC 6, BDBD 5, BEBE 4, CDCD 9, DEDE 3, DFDF 10 and EFEF 6.

(a) Use Kruskal's algorithm to find the minimum spanning tree, and state its total length.

(b) Use Prim's algorithm, starting at AA, and give the order in which the edges are added.

Worked solution: worked example

Answer: (a) DEDE, ACAC, BEBE, BCBC, EFEF, total 2323 km (b) ACAC, BCBC, BEBE, DEDE, EFEF

Step 1 - List the edges in order of length.

DE 3,AC 4,BE 4,BD 5,BC 6,EF 6,AB 7,CD 9,DF 10.DE\ 3,\quad AC\ 4,\quad BE\ 4,\quad BD\ 5,\quad BC\ 6,\quad EF\ 6,\quad AB\ 7,\quad CD\ 9,\quad DF\ 10.

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 DEDE, ACAC and BEBE, which join separate vertices. Reject BDBD (5): BB and DD are already joined through EE, so it would make the cycle BB, DD, EE. Add BCBC, which joins the groups {B,D,E}\{B,D,E\} and {A,C}\{A,C\}. Add EFEF, which brings in FF. The tree now has 55 edges for 66 vertices, so it is complete. M1 - Add edges in order of length, rejecting any that makes a cycle R1 - BDBD is rejected because it would form the cycle BB, DD, EE A1 - Edges DEDE, ACAC, BEBE, BCBC, EFEF

Why? An edge whose two ends are already connected would create a cycle, so it is rejected. A spanning tree on 66 vertices has 6−1=56-1=5 edges, which is the signal to stop.

Step 3 - Find the total length.

The tree is DEDE, ACAC, BEBE, BCBC, EFEF, and its total length is 3+4+4+6+6=23 km.3+4+4+6+6=23\text{ km}. A1 - 2323 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 AA.

From AA the shortest edge is ACAC (4). The tree {A,C}\{A,C\} is next joined by its shortest edge, BCBC (6), then BEBE (4) joins EE, then DEDE (3) joins DD, then EFEF (6) joins FF. The order is AC, BC, BE, DE, EF,AC,\ BC,\ BE,\ DE,\ EF, with total 4+6+4+3+6=234+6+4+3+6=23 km. M1 - Start at AA and add the shortest edge from the tree to a new vertex each time A1 - Order ACAC, BCBC, BEBE, DEDE, EFEF

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.

Marks (6):
M1 Add edges in order of length, rejecting any that makes a cycle
R1 BDBD is rejected because it would form the cycle BB, DD, EE
A1 Edges DEDE, ACAC, BEBE, BCBC, EFEF
A1 2323 km
M1 Start at AA and add the shortest edge from the tree to a new vertex each time
A1 Order ACAC, BCBC, BEBE, DEDE, EFEF

Now you try: enter your answers to be marked

1
Easy
No calc
[2 marks]
A minimum spanning tree of a graph has 4 edges with weights 2, 5, 7, and 3.

Find the total weight of the minimum spanning tree.
[2]
Fractions & powers
Other

Worked solution: practice question 1

2
Medium
No calc
[2 marks]
In applying Kruskal's algorithm, the edges so far selected are {AB, CD, BC}. The next cheapest edge is AC with weight 5.
Explain whether AC should be added, and state what check Kruskal's performs.
[2]
Fractions & powers
Other

Worked solution: practice question 2

3
Easy
No calc
[2 marks]
A connected graph has 8 vertices.

Find the number of edges in any spanning tree of this graph.
[2]
Fractions & powers
Other

Worked solution: practice question 3

Your score so far: 0 out of 6 marks

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.

Try some questions on minimum spanning tree

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 3(2.4)2−5×1.83(2.4)^2 - 5 \times 1.8 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 3(2.4)3(2.4). If a fraction, square root or power template is on the screen, press ▶ to move out of it before you carry on typing.

8.288.28

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.

9.5229.522, which is 9.529.52 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

CodeSyllabus content
AHL3.14Graphs: 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.16Walks, 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 nn vertices always has exactly n−1n-1 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 2E2E, 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 44 vertices has 66 edges, but a Hamiltonian cycle in it uses only 44.

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 AB=2AB=2, BC=2BC=2 and AC=3AC=3, the minimum spanning tree uses ABAB and BCBC with weight 44, but the shortest path from AA to CC is the single edge ACAC of weight 33.

Does an even degree sum guarantee that a simple graph exists?

No. For example, 3,3,3,13, 3, 3, 1 has sum 1010, but on 44 vertices each vertex of degree 33 must be joined to every other vertex, which would give the last vertex degree 33, not 11.

Ready to practise properly?

Practice questions on every section, marked instantly like the real exam.