RevisionDojo

AHL 3.14—Graph theory - IB Questionbank | RevisionDojo

Practice AHL 3.14—Graph theory with authentic IB Mathematics Applications & Interpretation (AI) exam questions for both SL and HL students. This question bank mirrors Paper 1, 2, 3 structure, covering key topics like core principles, advanced applications, and practical problem-solving. Get instant solutions, detailed explanations, and build exam confidence with questions in the style of IB examiners.

Paper

Level

Question 1

HLPaper 2

A graph has the degree sequence:

\{5,5,4,3,3,2,2,2\}

Is this a valid simple graph? Justify using the Havel-Hakimi algorithm.

[4]

How many edges does the graph contain?

[1]

Question 2

HLPaper 2

What is the minimum number of edges in a connected graph with 6 vertices?

[2]

Question 3

HLPaper 2

A graph G has an adjacency matrix A . You are told that the entry $\mathrm{A}_{i, j}^{3}=4$ .

What does this entry represent?

[2]

How can this information be used in analyzing graph connectivity?

[3]

Question 4

HLPaper 2

A graph has 5 vertices. Its adjacency matrix squared is:

A^{2}=\left[\begin{array}{lllll} 2 & 3 & 1 & 0 & 1 \\ 3 & 4 & 2 & 1 & 0 \\ 1 & 2 & 2 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 2 \end{array}\right]

What does the entry $\mathrm{A}_{2,3}^{2}=2$ tell you about the graph?Interpret your answer.

[4]

Question 5

HLPaper 2

How many different spanning trees exist in a complete graph with 5 vertices?

[5]

Question 6

HLPaper 2

Consider the following weighted graph:

Use Dijkstra's Algorithm to find the shortest path from vertex A to E. Show all steps.

[4]

Question 7

HLPaper 2

Consider the adjacency matrix of a graph with 4 vertices:

A=\left[\begin{array}{llll} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array}\right]

How many edges does the graph have?

[1]

Is the graph Eulerian?

[2]

Question 8

HLPaper 2

A connected graph has 9 vertices and 14 edges.

Find the number of ${ }^{* *}$ independent cycles** in the graph.

[2]

What is the minimum number of edges that must be removed to turn it into a tree?

[1]

Explain why every connected graph with v vertices and v or more edges must contain at least one cycle.

[2]

Question 9

HLPaper 2

A graph has the following degree sequence: $\{3,3,2,2,2,2\}$

Can this be a simple graph (no loops or multiple edges)? Justify your answer.

[4]

Question 10

HLPaper 2

Consider the following undirected graph:

Find the degree of vertex B .

[2]

AHL 3.14—Graph theory Questionbank