IB Maths AI HL Graph Theory Paper 1 & 2 Vertices & edges ~8 min read

Introduction to Graph Theory

A graph is just a set of dots (called vertices) joined by lines (called edges). It’s the maths of connections — how things are linked, not where they are. Whether you’re modelling a road network, a friendship circle, or a flight map, the same vocabulary works: count the vertices, count the edges, count how many edges meet at each vertex (its degree), and apply the Handshaking Lemma: the sum of all degrees is always twice the number of edges.

📘 What you need to know

Graph G = (V, E): a set of vertices V joined by a set of edges E. We write |V| for the number of vertices and |E| for the number of edges.
Degree deg(v): the number of edges meeting at vertex v. A loop (edge from a vertex to itself) counts twice.
Handshaking Lemma: Σ deg(v) = 2|E| — the total of all degrees is always even, and equals double the edge count.
Simple graph: no loops and no multiple edges between the same pair. Multigraph: loops or repeated edges allowed.
Connected graph: there is a path between every pair of vertices. Disconnected: at least one vertex can’t be reached from another.
Complete graph K_n: every pair of n vertices is joined; has n(n−1)2 edges.
Subgraph: a graph formed by taking some vertices and some edges from G.
Tree: a connected graph with no cycles — satisfies |E| = |V| − 1.
Walks, trails, paths, cycles: ways of travelling along edges, distinguished by what you’re allowed to repeat (see Section 2).

Vertices, edges, and degree

Think of a graph as a map of relationships. The vertices are the things (people, cities, websites, atoms), and the edges are the connections (friendships, roads, hyperlinks, bonds). The picture doesn’t have to be drawn neatly — only which vertices are joined matters, not where they sit on the page. Two graphs that look different but have the same connections are the same graph.

The degree of a vertex is simply how many edges touch it. Count the lines coming out of each dot — that’s the degree. A loop (an edge from a vertex back to itself) goes in and out of the same vertex, so it adds 2 to that vertex’s degree, not 1. Every edge has two ends, so when you add up the degrees of every vertex, you’re counting each edge twice. That’s the Handshaking Lemma.

Graph with 5 vertices and 7 edges. Degrees: 2, 3, 4, 3, 2 — their sum is 14, exactly twice the edge count. This is the Handshaking Lemma in action.

The Handshaking Lemma Σ deg(v) = 2|E| the sum of all vertex degrees equals twice the number of edges

Types of graphs, and how we travel through them

Different graphs come with different rules. A simple graph has no loops and no repeated edges — the cleanest, most common type, and what most exam questions use unless they say otherwise. A complete graph K_n takes n vertices and connects every pair, giving n(n−1)2 edges — the maximum possible for a simple graph. A connected graph has a route between every pair of vertices; if any vertex is cut off, the graph is disconnected. A tree is connected but has no cycles, and satisfies the neat rule |E| = |V| − 1.

To travel through a graph means moving from one vertex to another along edges. The travel words sound similar but mean different things:

Walk: any sequence of edges — vertices and edges may be repeated.
Trail: a walk where no edge is repeated (vertices may be).
Path: a walk where no vertex is repeated (so no edge can be either).
Circuit: a closed trail — starts and ends at the same vertex, no edge repeated.
Cycle: a closed path — starts and ends at the same vertex, no other vertex repeated.

Memory tip: walk is the loosest, path is the strictest. As you tighten the rules, you go walk → trail → path. Add “closed” (start = end) and you get circuit and cycle.

🧭 Recipe — analysing a graph

Count vertices and edges: |V| = number of dots, |E| = number of lines. Loops count as one edge each.
Find each degree: count edges meeting that vertex. Add 2 for every loop at that vertex.
Check Handshaking: Σ deg(v) should equal 2|E|. If not, recount.
Identify the type: simple (no loops, no repeats), complete (every pair joined), connected (all vertices reachable), tree (connected, no cycles).
For travel questions: list the vertex sequence, then check whether edges or vertices are repeated to classify as walk, trail, path, circuit, or cycle.

Worked examples

WE 1

List vertices, edges, and degrees

A graph G has edge set E = { AB, AC, BC, BD, CD }. List the vertices, find |V| and |E|, and give the degree of every vertex.

vertices appearing in E V = { A, B, C, D } → |V| = 4 |E| = 5 degrees (count each vertex’s edges) deg(A) = 2 (AB, AC) deg(B) = 3 (AB, BC, BD) deg(C) = 3 (AC, BC, CD) deg(D) = 2 (BD, CD) handshaking check Σ deg = 2 + 3 + 3 + 2 = 10 = 2 × 5 ✓ |V| = 4, |E| = 5 always do the handshaking check — it catches counting mistakes instantly.

WE 2

Find the missing degree using the Handshaking Lemma

A graph has 8 edges and 5 vertices with degrees 2, 3, 3, 4, and x. Find x.

apply the Handshaking Lemma Σ deg(v) = 2 |E| 2 + 3 + 3 + 4 + x = 2 × 8 12 + x = 16 x = 4 x = 4 no need to draw the graph — the lemma alone gives the answer.

WE 3

Show that a graph cannot exist

Determine whether a graph with five vertices having degrees 3, 3, 3, 3, and 3 can exist.

sum of degrees Σ deg = 3 + 3 + 3 + 3 + 3 = 15 by Handshaking, Σ deg must be even 15 is odd → contradiction no such graph exists rule of thumb: the number of vertices with odd degree is always even. Five odd-degree vertices breaks this.

WE 4

Edges in a complete graph

How many edges does the complete graph K₇ have? What is the degree of every vertex in K₇?

edges in K_n |E| = n(n − 1) / 2 = 7 × 6 / 2 = 21 degree in K_n: every vertex joins to the other n−1 deg(v) = 7 − 1 = 6 handshaking check Σ deg = 7 × 6 = 42 = 2 × 21 ✓ |E| = 21, deg(v) = 6 for every v in K_n every vertex has the same degree n − 1 — it’s called “regular”.

WE 5

Classify a sequence of vertices

In a graph with vertices { A, B, C, D, E } and edges { AB, BC, CD, DE, EA, AC }, classify each sequence as a walk, trail, path, circuit, or cycle (use the strictest label that applies):
(a) A → B → C → D → E
(b) A → B → C → A → E → D → C
(c) A → B → C → A

(a) A → B → C → D → E no vertex repeated, no edge repeated not closed (A ≠ E) (a) is a path (b) A → B → C → A → E → D → C edges used: AB, BC, CA, AE, ED, DC — all different but vertex C and A repeat → not a path (b) is a trail (not a path) (c) A → B → C → A no edge repeated, no vertex repeated (except start = end) closed (c) is a cycle work from the strictest label downwards: try “path” first, then “trail”, then “walk”.

WE 6

Tree property — number of edges

A tree has 12 vertices. How many edges does it have? If a new edge is added to the tree, what must happen?

tree formula |E| = |V| − 1 = 12 − 1 = 11 |E| = 11 edges adding an edge to a tree tree is already connected with no cycles a new edge joins two vertices already linked by a path a cycle is created a tree is the leanest possible connected graph — one extra edge forces a cycle, one missing edge disconnects it.

💡 Top tips

Always check the Handshaking Lemma after counting degrees — if the sum isn’t even, or doesn’t equal 2|E|, recount.
Loops count twice when computing degree — a vertex with a single loop and no other edges has degree 2, not 1.
The order of vertices doesn’t matter — edges {A, B} and {B, A} are the same edge in an undirected graph.
The drawing is just a picture — two graphs with the same vertex set and same edge set are equal even if drawn very differently.
For “could this graph exist” questions, check first that Σ deg is even; second that no degree exceeds |V| − 1 (in a simple graph).

⚠ Common mistakes

Counting a loop once in the degree — it contributes 2 to the degree, because both ends of the edge sit at the same vertex.
Confusing “trail” and “path”: a trail forbids edge repetition, a path forbids vertex repetition (which automatically forbids edge repetition).
Forgetting the ×2 in Handshaking: writing Σ deg = |E| instead of 2|E|.
Treating disconnected graphs as connected by accident — check that every vertex can reach every other vertex by some path.
Using n(n−1) instead of n(n−1)2 for K_n edges — the division by 2 prevents counting each edge from both ends.

Next up — Adjacency Matrices. Once you can describe a graph, the next step is storing it as a matrix: rows and columns indexed by vertices, with a 1 (or weight) where an edge exists. Powers of the adjacency matrix then count walks of given lengths between pairs of vertices — the gateway to all the powerful algorithmic graph theory in the IB AI HL course.

Need help with Graph Theory?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →