Graphs and networks

Count the dots, including the one at the top left that has only one edge. There are 6. The straight edge and the curved edge between the same two vertices are two edges, and neither adds a vertex.

(D) 7 is the number of edges. (A) 3 is the number of faces, since $6 + f - 7 = 2$ gives $f = 3$. (B) 5 misses the vertex of degree 1. 91.8% of students chose (C).

Test each word against the drawing. Every vertex can be reached from every other, so it is connected. Every edge carries a number, so it is weighted. There are no arrows, so it is not directed. The bottom two vertices are joined by two edges (9 and 8), so it is not simple.

Only (A) uses two words that both fit. (C) and (D) both say simple and miss the multiple edge. 55.4% of students chose (A), and 24.8% chose (D).

Each team is a vertex and each game is an edge. There are 18 ticks, but the table is symmetric: the game between the Bears and the Lions is ticked in the Bears row and again in the Lions row. So every game is counted twice:

$$\text{edges} = \frac{18}{2} = 9$$

This is the degree sum at work: six teams, each with degree 3, give $6 \times 3 = 18 = 2 \times 9$.

(D) 18 forgets to halve. (C) 15 is the complete graph, where every team plays every other team. (A) 6 is the number of vertices. 48.4% of students chose (B), and 31.4% chose (D).

T has no edges, but it is still a vertex of the graph, so it needs a row and a column of zeros. The triangle gives a 1 for each of QR, RS and QS, in both directions.

(A) leaves out T. (C) adds an edge from S to T because T is drawn close to S. (D) enters 2 for each edge, which counts each edge from both ends. The 2020 subject report has no multiple choice percentages.

a) E has one edge to A, one edge to B and two edges to D.

$$\deg(E) = 1 + 1 + 2 = 4$$

1 mark · correctly states the degree

b) The two curves between D and E are separate edges, so there are 2.

1 mark · correctly states the number of edges

c) Rows and columns in the order A, B, C, D, E. C is isolated, so its row and column are zeros. The loop at A is entered as 1.

$$\begin{array}{cl} & \hphantom{\left[\vphantom{\begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0\end{matrix}}\right.}\begin{matrix}\kern0.25em\mathclap{\text{A}}\kern0.25em & \kern0.25em\mathclap{\text{B}}\kern0.25em & \kern0.25em\mathclap{\text{C}}\kern0.25em & \kern0.25em\mathclap{\text{D}}\kern0.25em & \kern0.25em\mathclap{\text{E}}\kern0.25em\end{matrix} \\ \begin{matrix}\text{A} \\ \text{B} \\ \text{C} \\ \text{D} \\ \text{E}\end{matrix} & \left[\begin{matrix}1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 \\ 1 & 1 & 0 & 2 & 0\end{matrix}\right]\end{array}$$

1 mark · correctly completes entries for one row or one column in a 5 × 5 matrix

1 mark · correctly enters 1 for number of edges joining A to A

1 mark · completes adjacency matrix

The first mark may be implied by later working, and the last allows follow-through. The guide accepts equivalent matrices.

Check it: the matrix is symmetric, and rows B, C, D and E sum to their degrees (2, 0, 2, 4). Row A sums to 3, but deg(A) is 4, because the loop is entered as 1 and counts 2 towards the degree. That difference is expected, so do not “correct” it.

a) Eight edges: AE, AF, BC, BE, CD, CE, DE and EF.

$$\begin{array}{cl} & \hphantom{\left[\vphantom{\begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0\end{matrix}}\right.}\begin{matrix}\kern0.25em\mathclap{\text{A}}\kern0.25em & \kern0.25em\mathclap{\text{B}}\kern0.25em & \kern0.25em\mathclap{\text{C}}\kern0.25em & \kern0.25em\mathclap{\text{D}}\kern0.25em & \kern0.25em\mathclap{\text{E}}\kern0.25em & \kern0.25em\mathclap{\text{F}}\kern0.25em\end{matrix} \\ \begin{matrix}\text{A} \\ \text{B} \\ \text{C} \\ \text{D} \\ \text{E} \\ \text{F}\end{matrix} & \left[\begin{matrix}0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0\end{matrix}\right]\end{array}$$

1 mark · correctly completes entries for one row or one column in a 6 × 6 matrix with same horizontal and vertical labels

1 mark · correctly completes adjacency matrix

Check: symmetric, zeros on the diagonal, and the row sums 2, 2, 3, 2, 5, 2 add to 16, twice the 8 edges.

b) No loops or multiple edges, so it is simple. Every student is linked to every other through E, so it is connected. No arrows means not directed and no numbers means not weighted. Triangle A, E, F means the students cannot be split into two groups with every edge going across, so it is not bipartite.

1 mark · correctly identifies simple and connected only

c) The students who study an identical subject to C are the vertices joined to C: B, D and E.

1 mark · correctly identifies B, D and E only

d) Three edges from the graph, joined up, with no closed loop. The guide’s answer is the path F, A, E, C:

1 mark · correctly draws and labels a connected subgraph that contains student E and has three edges and no cycles

The guide accepts other valid subgraphs, such as AE, FE and EC. I count 31 that work. Three edges that make the triangle A, E, F fail, because that is a cycle.

Substitute into the formula book version and solve for $f$:

$$\begin{aligned} v + f - e &= 2 \\ 3 + f - 5 &= 2 \\ f &= 4 \end{aligned}$$

Three vertices need multiple edges to reach five edges, so this graph is not simple. Euler’s formula still applies, because it is connected and planar.

(A) 8 adds $v$ and $e$. (B) 6 is $v + e - 2$. (D) 2 is $e - v$. 82.6% of students chose (C).

Count the regions: the triangle A, B, C, the region bounded by A, C, B, D and E, the region between the arc and the left and bottom sides of the square, and the outside. That is 4.

Check with Euler’s formula. There are 5 vertices and 7 edges (AE, ED, DB, BA, AC, CB and the arc from A to D):

$$f = 2 - v + e = 2 - 5 + 7 = 4$$

(A) 3 forgets the outside face. (C) 5 is the number of vertices and (D) 7 the number of edges. 81.7% of students chose (B), and 10.0% chose (A).

Rearrange Euler’s formula for the edges:

$$e = v + f - 2 = 5 + 4 - 2 = 7$$

So look for a drawing with 5 vertices and 7 edges. (A) has exactly that, and its faces are the left, right and bottom triangles plus the outside.

(B) has 8 edges and 5 faces. Counting only its 4 enclosed triangles gives 4, which is the forgotten outside face again. (C) has only 4 vertices. (D) is a path with 4 edges and a single face. The 2020 subject report has no multiple choice percentages.

a) A planar graph can be drawn so that no edges cross each other.

1 mark · correctly defines a planar graph

The guide accepts equivalent statements, for example “can be embedded in the plane” or “can be drawn so edges only intersect at end points”.

b) Two triangles, the four-sided region on the left, the inside of the loop and the outside make 5 faces.

1 mark · correctly states the number of faces

c) There are 6 vertices and 9 edges. The loop is one edge.

$$\begin{aligned} v + f - e &= 6 + 5 - 9 \\ &= 2 \end{aligned}$$

1 mark · correctly identifies the number of vertices and edges for the graph

1 mark · shows Euler’s formula works for the graph

Showing it works means substituting your own counts and getting 2, with follow-through allowed. If you forget the outer face you get $6 + 4 - 9 = 1$, and if you count the loop’s face but not the loop you get $6 + 5 - 8 = 3$. Either result tells you to recount.

a) Graph 1 has 4 vertices, 5 edges and 3 faces: the two enclosed triangles and the outside.

$$v = 4, \quad f = 3, \quad e = 5$$

$$v + f - e = 4 + 3 - 5 = 2$$

1 mark · correctly identifies the number of vertices, faces and edges for graph 1

1 mark · applies Euler’s formula to graph 1

b) Two edges cross. Redraw it so that no edges cross.

1 mark · correctly identifies the feature to be changed

The 2023 report included its excerpts “to demonstrate statements that effectively describe that, to represent the graph as planar, its drawing should be changed so that no two edges cross”. Removing an edge would change the graph itself, so keep every edge.

c) Keep the pentagon and one diagonal, and take the other diagonal around the outside.

1 mark · correctly draws graph 2 as a simple connected graph with seven edges that do not cross and five vertices (one degree 2 vertex, four degree 3 vertices)

The descriptor is your check: still 5 vertices, still 7 edges, the same degrees. The redraw has $f = 2 - 5 + 7 = 4$ faces.

No repeated edges makes it at least a trail. Repeated vertices rule out a path. So it is a trail, an open trail in 2025 wording. A bridge and a loop are single edges, not routes.

50.1% of students chose (D), and 37.0% chose (C), path, missing that the vertices repeat.

a) It starts at A and finishes at B, so it is open. It travels F to C and then straight back C to F, so edge FC is repeated, which makes it only an open walk.

1 mark · correctly identifies an open walk

b) It starts and finishes at A, so it is closed. The edges AF, FC, CE, EF, FB and BA are all different, but F is visited twice. No repeated edge with a repeated vertex makes a trail, so it is a closed trail (a circuit).

1 mark · correctly identifies a closed trail

c) It is closed, and no edge or vertex repeats apart from returning to A, so it is a cycle.

1 mark · correctly identifies a cycle

The guide’s reasoning, shown in grey as not required, names what repeats in each case, such as “edge repeats: FC = CF”. Writing the reason takes a few seconds and makes your answer easy to check.

A loop adds 2 to a degree. A has degree 3 (its loop plus AB), B 2, C 2 and D 3 (its loop plus CD). A and D are the two odd vertices. Adding edge AD makes both 4, so every vertex is even and the graph is Eulerian.

(A) changes B from 2 to 4, and A and D stay odd. (B) changes A from 3 to 1, still odd. (D) leaves degrees 3, 1, 1 and 3 and splits the graph in two, so it is not even connected. 84.2% of students chose (C).

a) Start at R, go to W, across to P, along the top to D and down to R: RWPDR. No vertex repeats apart from the return to R, and it passes through R and P.

1 mark · correctly identifies one cycle

The guide accepts other cycles and starting points, for example RWCPDR, PDRWCP, PDRWP, RWBCPDR and PDRWBCP.

b) Count the degrees, remembering the two double edges (D to P, and R to W): B 2, C 3, D 4, P 4, R 3, W 6. Check: $2 + 3 + 4 + 4 + 3 + 6 = 22 = 2 \times 11$ edges.

Exactly two vertices, C and R, have odd degree and the rest are even. So the graph has an Eulerian trail, between C and R, but no Eulerian circuit. The graph is semi-Eulerian.

1 mark · correctly identifies the graph as semi-Eulerian

1 mark · justifies the decision

If you count each double edge once, you get D 3, P 3, R 2 and W 5, four odd vertices and the wrong answer. One trail that works is RDPDWPCWRWBC.

c) Rows and columns in the key order B, C, D, P, R, W:

$$\begin{array}{cl} & \hphantom{\left[\vphantom{\begin{matrix}0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0\end{matrix}}\right.}\begin{matrix}\kern0.25em\mathclap{\text{B}}\kern0.25em & \kern0.25em\mathclap{\text{C}}\kern0.25em & \kern0.25em\mathclap{\text{D}}\kern0.25em & \kern0.25em\mathclap{\text{P}}\kern0.25em & \kern0.25em\mathclap{\text{R}}\kern0.25em & \kern0.25em\mathclap{\text{W}}\kern0.25em\end{matrix} \\ \begin{matrix}\text{B} \\ \text{C} \\ \text{D} \\ \text{P} \\ \text{R} \\ \text{W}\end{matrix} & \left[\begin{matrix}0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 2 & 1 & 1 \\ 0 & 1 & 2 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 2 \\ 1 & 1 & 1 & 1 & 2 & 0\end{matrix}\right]\end{array}$$

1 mark · correctly constructs a valid adjacency matrix with same horizontal and vertical labels

1 mark · correctly determines values in the adjacency matrix

The 2s are the double edges. The diagonal is all 0 because there are no loops, the matrix is symmetric, and each row sums to the degree from part b).

Three ideas are hiding in this question: Pythagoras for the missing walkway, the Eulerian degree condition to find the closed walkway, and speed to turn distance into time. The stem names the Eulerian trails but leaves the other two for you to spot.

The missing walkway. AB and BC are perpendicular, so AC is the hypotenuse of the right-angled triangle ABC:

$$\begin{aligned} AC^2 &= 208^2 + 105^2 \\ &= 54\,289 \\ AC &= 233\ \text{m} \end{aligned}$$

1 mark · correctly calculates the distance for the walkway between A and C

Use AB and BC, the two sides that meet at the right angle at B. The 140 m walkways belong to triangle CDE and play no part.

The usual walk. Degrees: A 3, B 2, C 4, D 2, E 3. A and E are the only odd vertices, so an open Eulerian trail must start at one and finish at the other. Starting at A, it ends at E, for example ABCDECAE.

1 mark · correctly identifies an open Eulerian trail starting at A as a possible route for Helen’s usual daily walk

The guide accepts other trails from A to E, such as ABCDEACE, ACBAEDCE, ACBAECDE, ACDECBAE and ACEDCBAE, or a trail shown with arrows on the diagram.

Tuesday. A closed Eulerian trail needs every degree even. Closing a walkway lowers the degree at both its ends by 1, so the only walkway that makes A and E even without making anything else odd is AE (105 m). Tuesday’s route is ABCDECA.

1 mark · correctly identifies the closed Eulerian trail starting at A as the route for Helen’s walk on Tuesday

Distances. The usual walk covers every walkway once:

$$\begin{aligned} &208 + 105 + 140 + 140 \\ &\quad + 208 + 233 + 105 \\ &= 1139\ \text{m} \end{aligned}$$

On Tuesday walkway AE is closed:

$$1139 - 105 = 1034\ \text{m}$$

1 mark · determines total distance for Helen’s usual daily walk

1 mark · determines total distance for Helen’s walk on Tuesday

Calculate, compare, conclude. Find her speed from the usual walk, then the time for Tuesday:

$$\begin{aligned} \text{speed} &= \frac{1139}{17} = 67\ \text{m/min} \\ \text{time} &= \frac{1034}{67} = 15.4\ \text{min} \end{aligned}$$

1 mark · provides mathematical reasoning or working to support the decision

$15.4 > 15$, so Helen did not complete her walk on Tuesday in under 15 minutes.

1 mark · provides decision

The decision mark “can only be awarded if prior working supports decision”, so a bare “no” earns nothing. Follow-through is allowed on the distances, and the guide accepts alternative reasoning. One alternative: the 105 m Helen skips takes $105 \div 67 = 1.6$ minutes, and $17 - 1.6 = 15.4$.

Each number in the table is a road and each dash means no direct road. That gives 6 towns and 9 roads.

1 mark · correctly represents the connected towns as a network

1 mark · correctly includes lengths on the network

List the routes from M to F, shortest first:

Every other route is longer still.

1 mark · determines shortest current path

$$16 + 12 + 10 + 15 = 53\ \text{km}$$

1 mark · identifies length of shortest path

$$53 - 4 = 49\ \text{km}$$

1 mark · determines new road length

Follow-through applies to the last three marks, and the shortest path mark can be implied by later working. MVAF at 54 km is only 1 km longer, which is why a careful list matters.

Six numbers in the table means six edges. Waiben, Palilug and Keriri each have only two edges, so a Hamiltonian cycle must use both edges at each of them. That already closes the cycle: Waiben, Gealug, Palilug, Keriri, Ngurapai and back to Waiben. The 28-minute edge between Ngurapai and Gealug is the only one left out.

1 mark · correctly constructs a graph showing all 5 labelled vertices and all 6 edges

1 mark · correctly shows weights on all 6 edges

1 mark · identifies a Hamiltonian cycle beginning at Waiben

$$\begin{aligned} &14 + 16 + 25 + 20 + 18 \\ &= 93\ \text{min} \end{aligned}$$

1 mark · determines total travel time

The guide also accepts the reverse, WNKPGW, the cycle shown on the graph, and the time as 1 h 33 min. The 2024 report’s excerpt was chosen for “listing the vertex sequence and showing the sum calculation for the total travel time”.

Every pair of locations has a road, so the graph is complete: 5 vertices and 10 edges.

1 mark · correctly represents the road network in a graph showing all 10 edges with correct weights

A round trip from S that visits T, U, V and W once each is a Hamiltonian cycle. Each cycle and its reverse are the same trip, which leaves 12 to check:

1 mark · identifies shortest closed walk from S

$$\text{distance} = 3 + 4 + 2 + 6 + 10 = 25\ \text{km}$$

1 mark · determines total distance for shortest closed walk from S

$$\text{allowance} = 25 \times 0.80 = \text{\textdollar}20$$

1 mark · determines total driving allowance

$$\begin{aligned} \text{machines} &= 2 + 3 + 4 + 3 = 12 \\ \text{payment} &= 12 \times \text{\textdollar}25 + \text{\textdollar}20 \\ &= \text{\textdollar}320 \end{aligned}$$

1 mark · determines total payment

Follow-through is allowed from the closed walk onwards. The guide accepts the closed walk marked on the graph, and the payment in other units, such as 32 000 cents.

The guard checks every site once and starts and ends at A, so the route is a Hamiltonian cycle. All eight vertices have odd degree, so there is no Eulerian trail, which confirms this is about visiting sites, not covering roads.

First turn the labels into lengths. With $t_1 = 1$ and a common difference of 2:

$$t_2 = 3, \quad t_3 = 5, \quad 2t_1 = 2, \quad 2t_2 = 6, \quad t_1 + t_2 = 4$$

1 mark · correctly applies arithmetic sequence to determine all road lengths

There are five Hamiltonian cycles from A, counting each cycle and its reverse once:

1 mark · identifies Hamiltonian cycle beginning at A

$$\begin{aligned} &3 + 2 + 3 + 4 + 3 + 5 + 3 + 3 \\ &= 26\ \text{km} \end{aligned}$$

1 mark · calculates shortest total distance

$$\begin{aligned} t &= \frac{d}{s} = \frac{26}{40} \\ &= 0.65\ \text{h} = 39\ \text{min} \end{aligned}$$

1 mark · calculates total time to drive shortest distance

$$8 \times 15 = 120\ \text{min}$$

1 mark · calculates total time spent at eight sites

$$39 + 120 = 159\ \text{min} = 2\ \text{h}\ 39\ \text{min}$$

1 mark · calculates total time for patrol

$$9{:}00\ \text{am} + 2\ \text{h}\ 39\ \text{min} = 11{:}39\ \text{am}$$

1 mark · determines time of day

The eight sites include A, so the checking time is $8 \times 15$ minutes. Follow-through is allowed after the cycle, several marks may be implied by later working, and the guide accepts “2 h 39 min after 9:00 am” for the last mark.