Graph theory: basic concepts

IB Mathematics AI HL· 7 min read

1. Core Graph Components★☆☆☆☆⏱ 15 min

📘 Definition

Graph

G = (V, E)

A mathematical structure consisting of a set of vertices (nodes) $V$ that represent objects, and a set of edges $E$ that connect pairs of vertices to represent relationships between them.

Example:

A graph can model social media users (vertices) and friendships (edges).

Beyond the basic graph structure, there are several key terms you must memorize for exams:

- Vertex (node): A single point representing an object, often labelled $A, B, C$ .
- Edge: A connection between two vertices; edges can be undirected (mutual) or directed (one-way).
- Loop: An edge that connects a vertex to itself.
- Degree of a vertex: The number of edges connected to the vertex; a loop contributes 2 to the degree.

📐 Worked Example

For the undirected graph with vertices $A, B, C$ and edges: $A B, A C, B C, C C$ (a loop at $C$ ), find the degree of each vertex.

1
Count edges connected to vertex $A$ : $A$ has 2 edges, so:
2
$\deg(A) = 2$
3
Count edges connected to vertex $B$ : $B$ has 2 edges, so:
4
$\deg(B) = 2$
5
Count edges connected to vertex $C$ : $C$ has 2 regular edges plus 1 loop. A loop adds 2 to the degree, so:
6
$\deg(C) = 1 + 1 + 2 = 4$

2. Graph Classifications★☆☆☆☆⏱ 15 min

Graphs are classified by their edge properties and structure. The most common classifications for IB AI HL are below:

📘 Definition

Simple Graph

A simple undirected graph has no loops and no multiple edges between the same pair of vertices. Most basic graph problems use simple graphs.

- Undirected Graph: Edges have no direction, relationships are mutual (e.g., friendship).
- Directed Graph (digraph): Edges have a direction from one vertex to another (e.g., one-way social media follows).
- Weighted Graph: Each edge has an associated numerical weight (e.g., distance between two cities).
- Connected Graph: There is a path between every pair of vertices, no isolated components.

📐 Worked Example

Classify the graph that models a network of one-way streets between 4 city intersections.

1
Streets are one-way, so edges have a clear direction from one intersection to another.
2
There can be multiple one-way streets between the same pair of intersections, so the graph is not simple.
3
If the graph includes the length of each street as a value, it is also weighted. Conclusion:
4
The graph is a connected, directed, non-simple (weighted) graph.

Exam tip:

Always check for loops when classifying a simple graph — even one loop means it cannot be simple.

3. The Handshaking Lemma★★☆☆☆⏱ 20 min

The handshaking lemma is a fundamental property of all undirected graphs that relates the sum of vertex degrees to the total number of edges.

📘 Definition

Handshaking Lemma

\sum_{v \in V} \deg(v) = 2|E|

For any undirected graph, the sum of the degrees of all vertices equals twice the number of edges. This works because every edge contributes exactly 2 to the total degree sum, one for each vertex it connects.

📐 Worked Example

An undirected simple graph has 4 vertices with degrees 1, 2, 3, and 2. How many edges does it have?

1
First, sum the degrees of all vertices:
2
$1 + 2 + 3 + 2 = 8$
3
Apply the handshaking lemma: the sum equals twice the number of edges:
4
$8 = 2|E|$
5
Solve for $∣ E ∣$ (number of edges):
6
$|E| = 4$

✓ Quick check

Test your understanding:

Can an undirected graph have 5 vertices, all with odd degree?
- Yes
- No
Reveal answer
1 —
The sum of 5 odd numbers is odd. The handshaking lemma requires the sum of degrees to be equal to $2∣ E ∣$ , which is always even, so this is impossible.

4. Graph Representations★★★☆☆⏱ 20 min

Graphs can be represented numerically in two common examinable formats: adjacency matrices and adjacency lists.

📘 Definition

Adjacency Matrix

A

For a graph with $n$ vertices, an adjacency matrix is an $n \times n$ matrix where entry $A_{ij}$ is the number of edges between vertex $i$ and vertex $j$ . For directed graphs, $A_{ij}$ is the number of edges from $i$ to $j$ .

📐 Worked Example

Write the adjacency matrix for the undirected graph with vertices $V = {A, B, C}$ and edges $A B, A C, C C$ .

1
Order vertices as $A$ (row 1), $B$ (row 2), $C$ (row 3). Fill entries by counting edges between each pair:
2
$A$ connects to $B$ and $C$ , no loop: $A_{11} = 0, A_{12} = 1, A_{13} = 1$
3
$B$ connects to $A$ and $C$ , no loop: $A_{21} = 1, A_{22} = 0, A_{23} = 1$
4
$C$ connects to $A$ , $B$ , and has a loop: $A_{31} = 1, A_{32} = 1, A_{33} = 1$ (entry counts 1 for the loop in adjacency matrices)
5
The final adjacency matrix is:
6
$\begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}$

An adjacency list is a simpler representation for sparse graphs: it lists each vertex and all its adjacent vertices. For the example above, the adjacency list is: $A : [B, C], B : [A, C], C : [A, B, C]$ .

5. Common Pitfalls

Wrong move:

Counting a loop as contributing 1 to the degree of a vertex instead of 2

Why:

The handshaking lemma relies on every edge contributing 2 to the total degree, even loops, since they start and end at the same vertex

Correct move:

Always add 2 to the vertex degree when counting a loop

Wrong move:

Assuming all exam graphs are simple with no loops or multiple edges

Why:

Exam questions often give non-simple graphs, and misclassification leads to wrong degree counts and adjacency matrix entries

Correct move:

Always explicitly check for loops and multiple edges before starting calculations

Wrong move:

Swapping rows and columns in an adjacency matrix for a directed graph

Why:

Entries are defined as edges from the row vertex to the column vertex, so reversing gives incorrect connections

Correct move:

Confirm that $A_{ij}$ represents edges from row vertex $i$ to column vertex $j$ for directed graphs

Wrong move:

Accepting an odd sum of degrees as valid for an undirected graph

Why:

The handshaking lemma requires the sum of degrees to be even, as it equals twice the number of edges

Correct move:

If you get an odd sum, recheck your degree counting for a loop counting error

Wrong move:

Accepting a non-symmetric adjacency matrix for an undirected graph

Why:

If an edge connects $A$ to $B$ , it also connects $B$ to $A$ , so the matrix must be symmetric across the main diagonal

Correct move:

If your adjacency matrix for an undirected graph is not symmetric, you have an entry error

6. Quick Reference Cheatsheet

Term	Key Rule/Definition	Notation
Graph	Set of vertices + set of edges	$G = (V, E)$
Degree of vertex	Number of connected edges; loop = 2	$de g (v)$
Handshaking Lemma	Sum of degrees = 2 × number of edges	$\sum de g (v) = 2∣ E ∣$
Simple Graph	No loops, no multiple edges	n/a
Adjacency Matrix	$n \times n$ matrix, entry = edges between $i, j$	$A_{ij}$
Directed Graph	Edges have one-way direction	Digraph
Weighted Graph	Edges have associated numerical weight	n/a

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2021 · 1
Construct adjacency matrix for graph
2022 · 2
Apply handshaking lemma to find edges
2023 · 1
Classify graph by type

What's Next

Basic graph concepts are the foundation for all further graph theory topics in IB AI HL, where you will apply these ideas to solve real-world optimization problems. The terminology and representation skills you learned here are required for every subsequent graph topic, so mastering these basics will make more advanced problems much easier to approach. Next, you will move on to finding paths and circuits in graphs, which are used to solve problems like route planning and network design. From there, you will study minimum spanning trees and shortest path algorithms, which are common exam questions that rely entirely on correctly understanding basic graph components.