# Graph theory: basic concepts

> IB Mathematics AI HL · IB Math AI HL
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-basic-concepts/

This sub-topic introduces the core building blocks of graph theory, a discrete math tool for modeling relationships between objects. You will learn key terminology, graph classifications, and basic properties that underpin all graph theory applications for IB AI HL.

**Prerequisites:** [Basic matrix arithmetic and notation](https://www.owlsprep.com/study/ib-math-ai-hl-u2-matrix-operations/)

## Learning objectives

- Identify and define core components of a graph: vertices, edges, loops, and degree
- Classify graphs by type (undirected/directed, simple/non-simple, weighted/unweighted)
- Apply the handshaking lemma to relate vertex degrees and number of edges
- Represent graphs using adjacency matrices and adjacency lists

## Core Graph Components

**Graph** — 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.

*Notation:* G = (V, E)

*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: $AB, AC, BC, CC$ (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$$

## Graph Classifications

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

**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.

## The Handshaking Lemma

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

**Handshaking Lemma** — 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.

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

**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$$

**Check your understanding**

Test your understanding:

1. Can an undirected graph have 5 vertices, all with odd degree?

   - Yes
   - No

   *Answer:* No

   *Why:* 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.

## Graph Representations

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

**Adjacency Matrix** — 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$.

*Notation:* A

**Worked example:** Write the adjacency matrix for the undirected graph with vertices $V = \{A, B, C\}$ and edges $AB, AC, CC$.

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], \quad B: [A, C], \quad C: [A, B, C]$.

## Common pitfalls

- **Wrong:** Counting a loop as contributing 1 to the degree of a vertex instead of 2
  - Why it fails: 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: Always add 2 to the vertex degree when counting a loop
- **Wrong:** Assuming all exam graphs are simple with no loops or multiple edges
  - Why it fails: Exam questions often give non-simple graphs, and misclassification leads to wrong degree counts and adjacency matrix entries
  - Correct: Always explicitly check for loops and multiple edges before starting calculations
- **Wrong:** Swapping rows and columns in an adjacency matrix for a directed graph
  - Why it fails: Entries are defined as edges from the row vertex to the column vertex, so reversing gives incorrect connections
  - Correct: Confirm that $A_{ij}$ represents edges from row vertex $i$ to column vertex $j$ for directed graphs
- **Wrong:** Accepting an odd sum of degrees as valid for an undirected graph
  - Why it fails: The handshaking lemma requires the sum of degrees to be even, as it equals twice the number of edges
  - Correct: If you get an odd sum, recheck your degree counting for a loop counting error
- **Wrong:** Accepting a non-symmetric adjacency matrix for an undirected graph
  - Why it fails: If an edge connects $A$ to $B$, it also connects $B$ to $A$, so the matrix must be symmetric across the main diagonal
  - Correct: If your adjacency matrix for an undirected graph is not symmetric, you have an entry error

## 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 | $\deg(v)$ |
| Handshaking Lemma | Sum of degrees = 2 × number of edges | $\sum \deg(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 |

## 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.

- [Graph theory: adjacency matrices, paths and cycles](https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-adjacency-matrices-paths/)
- [Spanning trees and minimum spanning tree algorithms](https://www.owlsprep.com/study/ib-math-ai-hl-u5-spanning-trees-and-minimum-spanning/)
- [Graph theory applications: CPP and TSP](https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-applications-cpp-and/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-ai-hl-u5-graph-theory-basic-concepts/