IB Mathematics: Applications and Interpretation · Topic 3 · Geometry and trigonometry
3.14 Graph theory
Describe a graph using vertices and edges, identify types of graph including trees and cycles, and interpret simple networks as graphs.
1/6A graph is a set of vertices joined by edges
- A graph is a set of vertices joined by edges
- The degree of a vertex counts its edges
- Simple graphs and complete graphs follow strict rules
- Weights and directions let graphs model real networks
- A connected graph has a path between any two vertices
- Cycles and trees are important special structures
- Check your recall
- Practice: 10 questions
Part 1 of 6: A graph is a set of vertices joined by edges
A railway map shows stations and the tracks between them. The exact distances on the map matter less than which stations connect. Graph theory studies this kind of connection.
A graph is made of points joined by lines. Each point is a vertex, also called a node. Each line is an edge.
The shape of the drawing does not matter. Only the connections do. In a friendship network, people are vertices and friendships are edges.
Key terms · tap one for its definition
graph
A graph is a set of vertices together with a set of edges, each edge joining two vertices.
vertex
A vertex, also called a node, is a point of a graph that edges can join.
edge
An edge is a line in a graph that joins one vertex to another.
Part 2 of 6: The degree of a vertex counts its edges
Take any vertex and count the edges that meet there. This count is its degree. Two vertices joined directly by an edge are adjacent.
Each edge has two ends, so it adds 1 to the degree of two vertices. Adding all the degrees therefore counts every edge twice. Let be the number of edges. Then the sum of the degrees is .
Worked example
Degrees and edges
- Count edges at each vertex: A has 3, B has 2, C has 2, D has 2 and E has 1.
- Add the degrees: .
- Compare with : there are 5 edges, so .
Answer: The degrees are 3, 2, 2, 2 and 1, with sum 10, which equals .
Key terms · tap one for its definition
degree
The degree of a vertex is the number of edges that meet at that vertex.
adjacent
Two vertices are adjacent if an edge joins them directly.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: B · Worked explanation
Part 3 of 6: Simple graphs and complete graphs follow strict rules
Some graphs allow a loop, which is an edge from a vertex back to itself. Some allow two edges between the same pair. A simple graph allows neither.
A complete graph is a simple graph where every pair of vertices is adjacent. With vertices it is written . Each vertex then has degree .
Using the sum of degrees, the number of edges in is .
Worked example
Edges in a complete graph
- Each vertex has degree .
- The sum of degrees is .
- Halve the sum, since : . This matches .
Answer: has 10 edges.
Key terms · tap one for its definition
simple graph
A simple graph has no loops and no more than one edge between any pair of vertices.
complete graph
A complete graph is a simple graph with vertices in which every pair of vertices is joined by an edge.
Part 4 of 6: Weights and directions let graphs model real networks
Real networks carry more information than simple connection. A road map records distances, and a one-way street allows travel in one direction only. Two extra features capture these facts.
In a weighted graph, each edge has a number called its weight. The weight might be a distance, a time or a cost.
In a directed graph, each edge has a direction shown by an arrow. An edge from A to B does not allow travel from B to A.
Real networks modelled as graphs
- Network
- Road map
- Vertices
- Towns
- Edges
- Roads
- Extra feature
- Weights: distances
- Network
- Social media
- Vertices
- Accounts
- Edges
- Follows
- Extra feature
- Direction: who follows whom
- Network
- Flight routes
- Vertices
- Airports
- Edges
- Routes
- Extra feature
- Weights: flight times
Key terms · tap one for its definition
weighted graph
A weighted graph is a graph in which every edge is assigned a number, called its weight.
directed graph
A directed graph is a graph in which each edge has a direction, shown by an arrow from one vertex to another.

Quick check
One question on the part you just read
Easy
Show answer and explanation
Answer: D · Worked explanation
Part 5 of 6: A connected graph has a path between any two vertices
Think of travelling along edges from one vertex to another. A path is such a journey that visits no vertex more than once.
If a path exists between every pair of vertices, the graph is a connected graph. Otherwise it splits into separate pieces.
A road network with one island town and no bridge is not connected. No path leads to that town.
Key terms · tap one for its definition
path
A path is a sequence of edges joining a starting vertex to an ending vertex that visits no vertex more than once.
connected graph
A connected graph is a graph in which there is a path between every pair of vertices.
Part 6 of 6: Cycles and trees are important special structures
Now consider a route that returns to its start. A cycle is a path that begins and ends at the same vertex. In a simple graph, the shortest cycle is a triangle with 3 edges.
A tree is a connected graph with no cycles. Removing any edge from a tree disconnects it. A tree network has exactly one route between any two vertices.
A tree with vertices has exactly edges. A connected graph with vertices and edges must be a tree.
Worked example
Spotting a tree
- A tree with 8 vertices has edges.
- The network is connected and has 7 edges, so it is a tree.
- A tree has no cycles.
Answer: The network contains no cycle.
Key terms · tap one for its definition
cycle
A cycle is a closed path that starts and ends at the same vertex and visits no other vertex more than once.
tree
A tree is a connected graph that contains no cycles.
Check your recall[15 marks]
6 written questions. Answer each one in your head or on paper, then open the mark scheme.
- 1.State[2 marks]
State what is meant by a simple graph and by a complete graph.
Show mark schemeHide mark scheme
Model answer
A simple graph has no loops and no repeated edges between a pair of vertices. A complete graph is a simple graph in which every pair of vertices is joined by an edge.
- 1 mark for stating that a simple graph has no loops and no repeated edges
- 1 mark for stating that a complete graph joins every pair of vertices
- 2.Calculate[2 marks]
A graph has six vertices with degrees 4, 3, 3, 2, 2 and 2. Calculate the number of edges.
Show mark schemeHide mark scheme
Model answer
The sum of degrees is . Since the sum is , .
- 1 mark for finding the sum of degrees as 16
- 1 mark for dividing by 2 to obtain 8 edges
- 3.Determine[3 marks]
Determine the number of edges in the complete graph .
Show mark schemeHide mark scheme
Model answer
Edges .
- 1 mark for using
- 1 mark for substituting
- 1 mark for obtaining 28 edges
- 4.Distinguish[2 marks]
Distinguish between a path and a cycle.
Show mark schemeHide mark scheme
Model answer
A path joins a start vertex to an end vertex and visits no vertex twice. A cycle is a path that returns to its starting vertex.
- 1 mark for stating that a path visits no vertex more than once
- 1 mark for stating that a cycle begins and ends at the same vertex
- 5.Deduce[3 marks]
A connected graph has 12 vertices and 11 edges. Deduce whether it contains a cycle, giving a reason.
Show mark schemeHide mark scheme
Model answer
A tree with 12 vertices has 11 edges. The graph is connected with 11 edges, so it is a tree. A tree has no cycles, so it contains no cycle.
- 1 mark for stating that a tree with 12 vertices has 11 edges
- 1 mark for concluding that the graph is a tree
- 1 mark for concluding that it has no cycle
- 6.Describe[3 marks]
Describe how a road map can be modelled as a weighted graph.
Show mark schemeHide mark scheme
Model answer
Each town is a vertex and each road is an edge joining two towns. Each edge is given a weight equal to the length of the road.
- 1 mark for stating that towns are vertices
- 1 mark for stating that roads are edges
- 1 mark for stating that weights represent distances

Practice this topic
10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)
0 right0 of 10 answered
Includes the 2 quick checks in the note above.
EasyState[1 mark]
Show answer and explanation
Answer: A · Worked explanation
MediumCalculate[1 mark]
Show answer and explanation
Answer: B · Worked explanation
MediumCalculate[1 mark]
Show answer and explanation
Answer: D · Worked explanation
MediumDetermine[1 mark]
Show answer and explanation
Answer: C · Worked explanation
MediumIdentify[1 mark]
Show answer and explanation
Answer: A · Worked explanation
HardDeduce[2 marks]
Show answer and explanation
Answer: B · Worked explanation
HardIdentify[2 marks]
Show answer and explanation
Answer: C · Worked explanation
HardDetermine[2 marks]
Show answer and explanation
Answer: B · Worked explanation