IB Questionbank

User interface language: English | Español

Date	November 2019	Marks available	1	Reference code	19N.3.AHL.TZ0.Hdm_4
Level	Additional Higher Level	Paper	Paper 3	Time zone	Time zone 0
Command term	Write down	Question number	Hdm_4	Adapted from	N/A

Question

$G$ is a simple, connected graph with eight vertices.

$H$ is a connected, planar graph, with $v$ vertices, $e$ edges and $f$ faces. Every face in $H$ is bounded by exactly $k$ edges.

Write down the minimum number of edges in $G$ .

[1]

a.i.

Find the maximum number of edges in $G$ .

[2]

a.ii.

Find the maximum number of edges in $G$ , given that $G$ contains an Eulerian circuit.

[2]

a.iii.

Explain why $2e = kf$ .

[2]

b.i.

Find the value of $f$ when $v = 9$ and $k = 3$ .

[3]

b.ii.

Find the possible values of $f$ when $v = 13$ .

[4]

b.iii.

Markscheme

7 (a tree) A1

[1 mark]

a.i.

$\frac{{8 \times 7}}{2}\left( {7 + 6 + 5 + 4 + 3 + 2 + 1} \right)$ (a complete graph) (M1)

$= 28$ A1

[2 marks]

a.ii.

$\frac{{8 \times 6}}{2}$ (since every vertex must be of degree 6) (M1)

$= 24$ A1

[2 marks]

a.iii.

counting the edges around every face gives $k f$ edges A1

but as every edge is counted in 2 faces R1

$\Rightarrow kf = 2e$ AG

[2 marks]

b.i.

using $v - e + f = 2$ with $v = 9$ M1

EITHER

substituting $2e = 3f$ into $2\left( 9 \right) - 2e + 2f = 4$ (M1)

substituting $e = \frac{{3f}}{2}$ into $9 - e + f = 2$ (M1)

THEN

$18 - f = 4$

$f = 14$ A1

[3 marks]

b.ii.

$2v - kf + 2f = 4$ (or equivalent) M1

when $v = 13$

$\left( {k - 2} \right)f = 22$ or $\left( {2 - k} \right)f = - 22$ A1

EITHER

$\left( {k - 2} \right)f = 1 \times 2 \times 11$ M1

substituting at least two of $k = 13{\text{, }}4{\text{, }}3$ into $f = \frac{{22}}{{k - 2}}$ (or equivalent) M1

THEN

$f = 2{\text{, }}11{\text{, 22}}$ (since $f > 1$ ) A1

[4 marks]

b.iii.

Examiners report

[N/A]

a.i.

[N/A]

a.ii.

[N/A]

a.iii.

[N/A]

b.i.

[N/A]

b.ii.

[N/A]

b.iii.

Syllabus sections

Topic 3—Geometry and trigonometry » AHL 3.14—Graph theory

Show 27 related questions

22M.3.AHL.TZ1.2f.i:
Find which town is last to be polluted. Justify your answer.
22M.3.AHL.TZ1.2f.ii:
Write down the number of days it takes for the pollution to reach the last town.
22M.3.AHL.TZ2.2d.ii:
Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.
22M.1.AHL.TZ1.13b:
Find the time at which the bearing of the ship from the harbour is $045 ˚$ .
20N.3.AHL.TZ0.Hdm_5b:
Find an expression for $e'$ in terms of $e$ .
21N.3.AHL.TZ0.1c.ii:
$q$ .
21N.3.AHL.TZ0.1c.i:
$p$ .
22M.3.AHL.TZ2.2e:
State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.
22M.3.AHL.TZ2.2d.i:
By using Kruskal’s algorithm, find the minimum spanning tree for $S$ , showing clearly the order in which edges are added.
21N.3.AHL.TZ0.1d.i:
Use the nearest neighbour algorithm to find two possible cycles.
21N.3.AHL.TZ0.1e.ii:
Hence state the value of the upper bound for Daniel’s travel time for the value of $x$ found in part (e)(i).
22M.1.AHL.TZ1.13a:
Write down an expression for the position vector $r$ of the ship, $t$ hours after $1 : 00 pm$ .
21N.3.AHL.TZ0.1b.i:
Use Prim’s algorithm, starting at vertex $B$ , to find the weight of the minimum spanning tree of the remaining graph. You should indicate clearly the order in which the algorithm selects each edge.
21N.3.AHL.TZ0.1e.i:
Find the least value of $x$ for which the edge $AF$ will definitely not be used by Daniel.
21N.3.AHL.TZ0.1b.ii:
Hence, for the case where $x < 9$ , find a lower bound for Daniel’s travel time, in terms of $x$ .
20N.3.AHL.TZ0.Hdm_5d:
$H$ is a simple graph with $v$ vertices and $e$ edges.

Given that both $H$ and its complement are planar and connected, find the maximum possible value of $v$ .
19N.3.AHL.TZ0.Hdm_4a.iii:
Find the maximum number of edges in $G$ , given that $G$ contains an Eulerian circuit.
19N.3.AHL.TZ0.Hdm_4b.ii:
Find the value of $f$ when $v = 9$ and $k = 3$ .
20N.3.AHL.TZ0.Hdm_5a:
Find the maximum possible value of $e$ .
19N.3.AHL.TZ0.Hdm_4b.iii:
Find the possible values of $f$ when $v = 13$ .
20N.3.AHL.TZ0.Hdm_5c:
Given that the complement of $G$ is also planar and connected, find the possible values of $e$ .
19N.3.AHL.TZ0.Hdm_4b.i:
Explain why $2e = kf$ .
19N.3.AHL.TZ0.Hdm_4a.ii:
Find the maximum number of edges in $G$ .
21N.3.AHL.TZ0.1c.iii:
$r$ .
21N.3.AHL.TZ0.1d.ii:
Find the best upper bound for Daniel’s travel time.
21N.3.AHL.TZ0.1a:
Write down a Hamiltonian cycle in $W$ .
21N.3.AHL.TZ0.1f:
The tourist office in the city has received complaints about the lack of cleanliness of some routes between the attractions. Corinne, the office manager, decides to inspect all the routes between all the attractions, starting and finishing at $H$ . The sum of the weights of all the edges in graph $W$ is $(92 + x)$ .

Corinne inspects all the routes as quickly as possible and takes $2$ hours.

Find the value of $x$ during Corinne’s inspection.

Hide related questions

Topic 3—Geometry and trigonometry

Question

Markscheme

Examiners report

Syllabus sections

View options