Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Mathematics: Applications and Interpretation
  3. ›3 Geometry and trigonometry
  4. ›3.14 Graph theory

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.

  • 5 min read
  • 6 parts
  • 10 questions
  • Draft
  • HL only
Start a Quick 5 on this topic→Jump to the 10 questions
1/6A graph is a set of vertices joined by edges
  1. 1A graph is a set of vertices joined by edges
  2. 2The degree of a vertex counts its edges
  3. 3Simple graphs and complete graphs follow strict rules
  4. 4Weights and directions let graphs model real networks
  5. 5A connected graph has a path between any two vertices
  6. 6Cycles and trees are important special structures
  7. Check your recall
  8. Practice: 10 questions
1

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.

Exam tip

Describe a graph by listing its vertices and edges. Write edge AB for the edge joining vertex A to vertex B.

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 1 done

2

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 EEE be the number of edges. Then the sum of the degrees is 2E2E2E.

Figure 1. The vertices are drawn as circles and the edges as lines joining them.

Worked example

Degrees and edges

A graph has vertices A to E and edges AB, AC, AD, BC and DE. Find the degree of each vertex and check the sum.
  1. 1
    Count edges at each vertex: A has 3, B has 2, C has 2, D has 2 and E has 1.
  2. 2
    Add the degrees: 3+2+2+2+1=103+2+2+2+1=103+2+2+2+1=10.
  3. 3
    Compare with 2E2E2E: there are 5 edges, so 2E=2×5=102E=2\times5=102E=2×5=10.

Answer: The degrees are 3, 2, 2, 2 and 1, with sum 10, which equals 2E2E2E.

Exam tip

Check your degrees by adding them. The total must be even, because it equals twice the number of edges.

Go deeperOdd degrees come in pairs

The sum of the degrees is always even, since it equals 2E2E2E. A sum of whole numbers is even only if an even number of them are odd.

So every graph has an even number of vertices with odd degree. A graph with exactly one such vertex cannot exist.

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.

Part 2 done

Quick check

One question on the part you just read

Easy

Identify the term for a line that joins two vertices of a graph.
Show answer and explanation

Answer: B · Worked explanation

A line joining two vertices is an edge. The degree is a count of edges at a vertex, a path is a sequence of edges, and a weight is a number attached to an edge.
3

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 nnn vertices it is written KnK_nKn​. Each vertex then has degree n−1n-1n−1.

Using the sum of degrees, the number of edges in KnK_nKn​ is n(n−1)2\frac{n(n-1)}{2}2n(n−1)​.

Worked example

Edges in a complete graph

Find the number of edges in K5K_5K5​.
  1. 1
    Each vertex has degree n−1=4n-1=4n−1=4.
  2. 2
    The sum of degrees is 5×4=205\times4=205×4=20.
  3. 3
    Halve the sum, since 2E=202E=202E=20: E=202=10E=\frac{20}{2}=10E=220​=10. This matches 5×42\frac{5\times4}{2}25×4​.

Answer: K5K_5K5​ has 10 edges.

Common mistake

The count is n(n−1)2\frac{n(n-1)}{2}2n(n−1)​, not n(n−1)n(n-1)n(n−1). Dividing by 2 stops each edge being counted twice.

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 KnK_nKn​ is a simple graph with nnn vertices in which every pair of vertices is joined by an edge.

Part 3 done

4

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

NetworkVerticesEdgesExtra feature
Road mapTownsRoadsWeights: distances
Social mediaAccountsFollowsDirection: who follows whom
Flight routesAirportsRoutesWeights: flight times
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.

Part 4 done

Quick check

One question on the part you just read

Easy

Identify the name of a graph in which every edge has a number attached to it.
Show answer and explanation

Answer: D · Worked explanation

A graph whose edges carry numbers is a weighted graph. A directed graph gives edges a direction rather than a number, and a complete graph joins every pair of vertices. Neither of those features puts a number on each edge.
5

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.

Common mistake

Edges that cross in a drawing do not create a vertex. Two crossing lines join the graph only if they meet at a vertex.

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 5 done

6

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 nnn vertices has exactly n−1n-1n−1 edges. A connected graph with nnn vertices and n−1n-1n−1 edges must be a tree.

Worked example

Spotting a tree

A network of 8 computers is connected, and 7 cables join them. Deduce whether it contains a cycle.
  1. 1
    A tree with 8 vertices has 8−1=78-1=78−1=7 edges.
  2. 2
    The network is connected and has 7 edges, so it is a tree.
  3. 3
    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.

Note read

Check your recall[15 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 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. 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 4+3+3+2+2+2=164+3+3+2+2+2=164+3+3+2+2+2=16. Since the sum is 2E2E2E, E=162=8E=\frac{16}{2}=8E=216​=8.

    • 1 mark for finding the sum of degrees as 16
    • 1 mark for dividing by 2 to obtain 8 edges
  3. 3.Determine[3 marks]

    Determine the number of edges in the complete graph K8K_8K8​.

    Show mark schemeHide mark scheme

    Model answer

    Edges =n(n−1)2=8×72=28=\frac{n(n-1)}{2}=\frac{8\times7}{2}=28=2n(n−1)​=28×7​=28.

    • 1 mark for using n(n−1)2\frac{n(n-1)}{2}2n(n−1)​
    • 1 mark for substituting n=8n=8n=8
    • 1 mark for obtaining 28 edges
  4. 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. 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. 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.

3.

Easy·State[1 mark]

State the degree of a vertex at which 3 edges meet.
Show answer and explanation

Answer: A · Worked explanation

The degree of a vertex is the number of edges that meet there, so it is 3. The value 6 would come from counting each edge at both ends, which belongs to the sum over the whole graph, not a single vertex.
4.

Medium·Calculate[1 mark]

A simple graph has 6 vertices, and every vertex has degree 3. Calculate the number of edges.
Show answer and explanation

Answer: B · Worked explanation

The sum of degrees is 6×3=186\times3=186×3=18, and this equals 2E2E2E, so E=9E=9E=9. The value 18 is the sum of the degrees, which counts each edge twice. Check: a graph with 9 edges has degrees adding to 18, which equals 6×36\times36×3.
5.

Medium·Calculate[1 mark]

Calculate the number of edges in the complete graph K6K_6K6​.
Show answer and explanation

Answer: D · Worked explanation

Use n(n−1)2=6×52=15\frac{n(n-1)}{2}=\frac{6\times5}{2}=152n(n−1)​=26×5​=15. The value 30 is n(n−1)n(n-1)n(n−1), which counts every edge twice. The value 36 is n2n^2n2, which would let every vertex join itself as well. Dividing n(n−1)=30n(n-1)=30n(n−1)=30 by 2 corrects the double count and leaves 15 edges.
6.

Medium·Determine[1 mark]

Determine the number of edges in a tree with 9 vertices.
Show answer and explanation

Answer: C · Worked explanation

A tree with nnn vertices has n−1n-1n−1 edges, so 9 vertices give 8 edges. The value 9 would leave a cycle, because a connected graph with as many edges as vertices cannot be a tree.
7.

Medium·Identify[1 mark]

A city has one-way streets. Identify the type of graph that models the street network best.
Show answer and explanation

Answer: A · Worked explanation

One-way streets allow travel in one direction only, which is what the arrows of a directed graph show. A weighted graph records numbers such as lengths, not direction. A complete graph joins every pair of vertices, which a street network does not do.
8.

Hard·Deduce[2 marks]

A connected graph has 6 vertices and 7 edges. Deduce the correct statement.
Show answer and explanation

Answer: B · Worked explanation

A tree with 6 vertices has exactly 5 edges. This graph has 7 edges, so it is not a tree, and a connected graph that is not a tree must contain a cycle. A complete graph on 6 vertices would need 15 edges.
9.

Hard·Identify[2 marks]

A student claims a simple graph exists with five vertices of degrees 4, 3, 3, 2 and 1. Identify the correct statement.
Show answer and explanation

Answer: C · Worked explanation

The degrees add to 13, but the sum must equal twice the number of edges, so it must be even. A vertex of degree 4 is allowed with five vertices, so the problem is the odd total, not that vertex.
10.

Hard·Determine[2 marks]

A complete graph KnK_nKn​ has 45 edges. Determine nnn.
Show answer and explanation

Answer: B · Worked explanation

Solve n(n−1)2=45\frac{n(n-1)}{2}=452n(n−1)​=45, so n(n−1)=90n(n-1)=90n(n−1)=90. Since 10×9=9010\times9=9010×9=90, n=10n=10n=10. The value n=9n=9n=9 gives 9×82=36\frac{9\times8}{2}=3629×8​=36 edges, so it is too small. Likewise n=11n=11n=11 gives 11×102=55\frac{11\times10}{2}=55211×10​=55 edges, which is too large. The value n=15n=15n=15 is far too big, since K15K_{15}K15​ has 105 edges.

Keep going

Next topic3.15 Adjacency matricesPrevious topic3.13 Scalar and vector products

More in Topic 3 · Geometry and trigonometry

  1. 3.8Unit circle and identitiesNotes · 10 questions· HL only
  2. 3.9Matrix transformationsNotes · 10 questions· HL only
  3. 3.10Vector conceptsNotes · 10 questions· HL only
  4. 3.11Vector equation of a lineNotes · 10 questions· HL only
  5. 3.12Vectors in kinematicsNotes · 10 questions· HL only
  6. 3.13Scalar and vector productsNotes · 10 questions· HL only
  7. 3.14Graph theoryNotes · 10 questions· HL only
  8. 3.15Adjacency matricesNotes · 10 questions· HL only
  9. 3.16Tree and cycle algorithmsNotes · 10 questions· HL only

All IB Mathematics: Applications and Interpretation topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/6 read

  1. 1A graph is a set of vertices joined by edges
  2. 2The degree of a vertex counts its edges
  3. 3Simple graphs and complete graphs follow strict rules
  4. 4Weights and directions let graphs model real networks
  5. 5A connected graph has a path between any two vertices
  6. 6Cycles and trees are important special structures
  7. Check your recall
  8. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe