What you practice
Each set draws new weighted networks with no crossing edges. Find a minimum spanning tree and its weight, say which edge Prim’s algorithm adds next, decide whether a tree is minimal, find the shortest path by inspection or with Dijkstra’s algorithm, and, for VCE, decide whether a route is an Eulerian trail or a Hamiltonian cycle. Paths are written the way your course writes them: ABFGD for HSC, A–B–F–G–D for VCE. Common slips from the examination reports get a note, such as a path that leaves out its start vertex or a longer route picked by eye.
Example: a minimum spanning tree with a tie
In set TREE32 (HSC) gravel roads join six towns. From the lightest up the edges are CF 7, DE 20, AB 30, BD 31, AD 31, DF 32, BC 38, CD 38 and EF 43 km. AD and BD tie at 31. Taking BD first, Kruskal’s algorithm takes CF, DE, AB and BD, skips AD because A and D are already joined through B, then takes DF: 7 + 20 + 30 + 31 + 32 = 120 km. Taking AD first instead gives a second minimum spanning tree, with AD in place of BD. Open set TREE32
Questions
How do you find a minimum spanning tree with Kruskal’s algorithm?
List the edges from the lightest up. Take each one unless it would make a cycle with the edges already taken. Stop when the tree has one edge fewer than the number of vertices. HSC Standard 2 allows Kruskal’s, Prim’s or inspection; the VCE study design names Prim’s algorithm or inspection.
How does Prim’s algorithm work?
Start at any vertex. At each step add the lightest edge that joins a vertex already in the tree to one that is not, and repeat until every vertex is joined. When two edges tie, either can be taken: the total weight comes out the same.
Can a network have more than one minimum spanning tree?
Yes, when weights are equal. If an edge left out weighs the same as a tree edge on the cycle it would close, the two can swap and the total stays the same. The 2024 HSC paper asked exactly this. When every weight is different, there is only one minimum spanning tree.
Does the shortest path have to visit every vertex?
No. It only has to join the two vertices named, and it can skip the rest. The 2023 HSC feedback noted answers that included every vertex. Add up the weights of each route rather than judging by eye: the diagrams are not drawn to scale.
How does Dijkstra’s algorithm work?
Give the start vertex 0. Each round, finish the unfinished vertex with the smallest label, then lower each neighbour’s label to that label plus the edge weight if that is smaller. When the end vertex is finished, its label is the shortest distance. The VCE study design names this algorithm; the HSC syllabus does not, but it finds the same path.
What is the difference between an Eulerian trail and a Hamiltonian path?
An Eulerian trail uses every edge exactly once; it needs exactly two odd vertices and runs from one to the other. An Eulerian circuit needs every vertex even. A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle also returns to the start. These are VCE topics.
Sources, read October 28, 2026: NESA HSC Mathematics Standard 2 papers, marking guidelines and feedback, 2025, 2024 and 2023; NSW Department of Education, Year 12 Mathematics Standard 2 networks resources; VCE General Mathematics study design; VCAA General Mathematics examinations and reports, 2023 to 2025.