Graph Basics: Vertices, Edges, Connections

IB Maths AI HL Course (Early Bird Access; Continuous Updates) | 24-Month Access

Section Navigation

Section Overview

This section introduces Graph Theory, a branch of mathematics used to model relationships between objects using vertices and edges. You will move from simple visual representations to technical analysis of weighted graphs, connectivity, and vertex degrees, forming the foundation for network optimization in Paper 2 and Paper 3 modeling tasks.

Why This Matters for AIHL Exams

Network Analysis: Whether modeling transit systems, social networks, or logistics, graph theory is the definitive tool for extracting efficiency from complex connections.
The Handshaking Lemma: This fundamental property ($$\sum \text{deg}(v) = 2e$$) is a high-frequency tool for solving “Show that” or “Determine if possible” questions in Paper 1 and 2.
Adjacency Translation: Mastering the transition between visual graphs and adjacency tables is a core procedural skill required for computer-based algorithms and modeling.

High-Score Focus (Level 6–7 Insight)

Directed Connectivity Nuance: Level 7 students distinguish between weakly and strongly connected directed graphs. To be “strongly connected,” you must be able to move in both directions between any two points following the arrows.
Impossible Graphs: If the sum of degrees in a proposed graph is odd, the graph cannot exist. Using the Handshaking Lemma to prove a scenario is impossible is a hallmark of a Level 7 student.
Arbitrary Placement: Don’t waste time trying to draw graphs to scale. Focus on the topology (the connections) rather than the physical distance between vertices, unless the graph is weighted.

By the End of This Section, You Should Be Able To:

Identify vertices and edges from adjacency tables or real-world descriptions.

Apply the Handshaking Lemma to verify the properties of a graph.

Interpret weighted graphs to find the cost or distance of specific walks.

Model physical networks using directed and undirected graphs.

Analyze connectivity to determine if a system is broken into subgraphs or is strongly connected.

Suggested Study Path

Internalize basic definitions: vertex, edge, and degree.
Practice converting tables to graphs; your drawing doesn’t need to be pretty, just accurate.
Study the Handshaking Lemma example to understand the link between degrees and edges.
Differentiate between walks and specific paths in directed graphs.
Review the TOK note on the Königsberg bridges to see the origins of this field.

Study Metrics

Core: 30–45 mins

Practice: 45–60 mins

Exam Priority: ★★★★☆

Constructing Graphs

In this section, we move away from statistical graphs and enter the field of Graph Theory. Here, a graph is a visual representation of relationships between objects. These objects could be physical locations, people, computer servers, or chemical compounds.

A graph consists of points, known as vertices (singular: vertex), and lines connecting them, known as edges. In mathematical graph theory, graphs do not have to be drawn to scale, and the physical positions of the vertices do not need to relate to their positions in the real world. A graph simply shows which vertices are directly connected.

Key Idea: Graph Definitions

A graph is defined as a set of vertices and a set of edges.

A vertex represents an object.
An edge joins two vertices.

TOK: The Seven Bridges of Königsberg

Have you heard of the Seven Bridges of Königsberg problem? Königsberg (now Kaliningrad, Russia) had seven bridges connecting two islands and the mainland. The puzzle was to walk across all seven bridges exactly once. Euler’s solution to this problem laid the foundation for all mathematical graph theory. Do all mathematical problems have a solution?

Weighted Graphs and Walks

Sometimes, the connections between vertices carry specific information, such as distance, cost, or time. A graph that shows values like these associated with its edges is called a weighted graph. The value assigned to an edge is called its weight.

Conversely, a graph that gives no information regarding the magnitude of the connections, only the existence of connections, is called an unweighted graph. An example is a map of the London Underground, which shows connections but not precise distances.

Definition: Walk

A walk is any sequence of vertices passed through when moving along the edges of the graph.

Information in an unweighted graph can also be contained in an adjacency table. In an adjacency table, the entries indicate the number of direct connections between two vertices.

Worked Example

The table shows the connections between stations on a small mountain railway. An empty cell indicates no direct connection between the stations.

	A	B	C	D
A		1	1
B	1		1
C	1	1		1
D			1

a. Show this information on a graph.

b. Write down two possible walks from A to D.

Solution

Part a: Constructing the Graph

To draw the graph, we begin by placing the vertices (A, B, C, D) on the page. The positions are arbitrary.

From the first row, A is connected to B and C. Draw edges AB and AC.
From the second row, B is connected to A and C. The edge BA is already drawn, so we add edge BC.
From the third row, C is connected to D (others are already drawn). Add edge CD.
The final row acts as a check; D is connected only to C.

Part b: Identifying WalksThere are infinitely many answers because you can pass through vertices multiple times. Simple examples include:

A direct route via C: A $\to$ C $\to$ D (denoted ACD)
A longer route via B: A $\to$ B $\to$ C $\to$ D (denoted ABCD)
A route revisiting vertices: A $\to$ B $\to$ A $\to$ C $\to$ D (denoted ABACD)

Worked Example

The table shows costs in dollars of travelling by bus between towns.

	A	B	C	D	E
A		4	7	6
B	4		5
C	7	5		3	6
D	6		3		2
E			6	2

Show this information on a graph.

Solution

Because the costs are given in the table, you must also show them on the graph. This will be a weighted graph.

We draw 5 vertices (A, B, C, D, E) and connect them according to the table, labelling each edge with its weight:

Connect A-B (weight 4), A-C (weight 7), A-D (weight 6).
Connect B-C (weight 5).
Connect C-D (weight 3), C-E (weight 6).
Connect D-E (weight 2).

Note that there are many different ways to draw the graph visually (e.g. vertices in a circle, vertices in a line, or random placement). Any depiction is fine so long as you show the correct connections and weights.

Conceptual Check

How do you construct a graph from information given in a table? What information can be readily obtained from a visual graph that cannot easily be seen in a table (e.g., disjointed parts or clusters)?

Graph Connectivity and Degrees

In the study of graph theory, understanding how vertices are linked—and the strength of those links—is fundamental. We classify graphs based on whether it is possible to travel between any two points within them.

Connected Graphs and Subgraphs

A graph is considered connected if a path (or walk) exists between any two vertices. If a graph is broken into disjoint parts where no path exists between them, it is unconnected. For example, if a graph has vertices $ A, B, C $ connected in a triangle, and separate vertices $ D, E $ connected to each other but not to $ A, B, $ or $ C $, the entire system represents an unconnected graph.

These isolated sections are known as subgraphs.

Definition: Connectivity

In a connected graph, it is possible to construct a walk between any two vertices.
A subgraph of a graph $ G $ consists entirely of vertices and edges that are also in $ G $.

Directed Graphs

In a directed graph (or digraph), every edge is assigned a specific direction, indicated by an arrow. The concept of connectivity is more nuanced here because travel is restricted to the direction of the arrows.

Definition: Directed Connectivity

A directed graph is connected (or weakly connected) if a walk can be constructed in at least one direction between any two vertices (ignoring arrow direction for the sake of connection).
A directed graph is strongly connected if it is possible to construct a walk in either direction between any two vertices.

TOK: Contextual Clarity

Except in cases where extra clarity is needed, the word “graph” will be taken to mean an undirected graph. If the graph is directed it will be explicitly mentioned. How does defining default assumptions aid in mathematical communication?

Degrees of Vertices

The degree (or order) of a vertex provides a measure of how connected that specific point is within the graph. It is simply a count of the edges attached to it.

Key Idea: Vertex Degree

The degree (or order) of a vertex in a graph is the number of edges with that vertex as an end point.

A vertex whose degree is an even number is called an even vertex or is said to have even degree.

In-degree and Out-degree

For directed graphs, we distinguish between edges arriving at a vertex and edges leaving it.

In-degree: The number of edges with that vertex as an end point (arrow pointing in).
Out-degree: The number of edges with that vertex as a starting point (arrow pointing out).

Exam Tip

When calculating the sum of degrees in any graph, you are counting every edge twice (once for each end). Therefore, the sum of all degrees in a graph is always equal to twice the number of edges. This is known as the Handshaking Lemma.

Worked Example

Five people shake hands before a meeting as indicated in the adjacency table below. An entry of ‘1’ indicates a handshake took place.

	A	B	C	D	E
A		1		1	1
B	1		1
C		1		1
D	1		1		1
E	1			1

a. Draw the graph representing these handshakes.

b. Find the degree of each vertex.

c. Verify the Handshaking Lemma for this graph.

Solution

Part a: The Graph

We draw 5 vertices $ A, B, C, D, E $ and connect them where a ‘1’ appears in the table.

A connects to B, D, E.
B connects to A, C.
C connects to B, D.
D connects to A, C, E.
E connects to A, D.

Part b: Degrees

Counting the edges connected to each vertex:

$\text{deg}(A) = 3$
$\text{deg}(B) = 2$
$\text{deg}(C) = 2$
$\text{deg}(D) = 3$
$\text{deg}(E) = 2$

The degree sequence is $ 3, 2, 2, 3, 2 $.

Part c: Handshaking Lemma

Sum of degrees:

$$\sum \text{deg}(v) = 3 + 2 + 2 + 3 + 2 = 12$$

Total number of edges (handshakes): Counting the unique connections (A-B, A-D, A-E, B-C, C-D, D-E) gives $ 6 $ edges.

$$2 \times \text{number of edges} = 2 \times 6 = 12$$

Since $ 12 = 12 $, the Handshaking Lemma holds.

Conceptual Check

Why is it impossible to construct a graph with degrees $ 1, 2, 2, 2, 2 $? (Hint: Sum the degrees and consider the Handshaking Lemma).

🎯 Examiner’s Radar: Graph Theory Fundamentals

📋 Paper Mapping

Paper 1 (Quick Proofs): Expect “State with a reason if such a graph exists.” Always use the Handshaking Lemma here. If the sum of degrees is odd, the graph is impossible.
Paper 2/3 (Modeling): Transitioning from a table to a weighted graph is a “pre-requisite” step. If you miss one edge or weight, your entire optimization (like finding the shortest path) will be wrong.

💡 Scoring Secrets

Connectivity Vocabulary: In directed graphs, don’t just say “it is connected.” Use “Strongly Connected” if you can go from any A to B and B to A following the arrows.
Adjacency Table Checks: In an undirected graph, the adjacency table must be symmetrical across the diagonal. Use this as a 5-second sanity check before drawing your graph.