Skip to main content
VICGeneral MathematicsSyllabus dot point

What are the key terms of graph theory, and how are spanning trees and shortest paths found in a weighted network?

Use graph and network terminology (vertices, edges, degree, connected, planar), apply Euler's formula and the handshake result, find a minimum spanning tree, and determine the shortest path through a weighted network

A focused answer to the VCE General Mathematics Unit 4 Networks key-knowledge point on graph fundamentals. Vertices, edges and degree, the handshake result, Euler's formula for planar graphs, minimum spanning trees, and finding the shortest path in a weighted network.

Generated by Claude Opus 4.76 min answer

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section
  1. What this dot point is asking
  2. Counting results
  3. Minimum spanning tree
  4. Shortest path
  5. Why this matters for the exams

What this dot point is asking

VCAA wants you to read and describe networks using correct graph terminology, apply two standard counting results (the handshake result and Euler's formula), find a minimum spanning tree that connects every vertex at least cost, and determine the shortest path between two vertices in a weighted graph. These are the building blocks of the Networks and decision mathematics module and appear on both exams.

Counting results

Two facts let you reason about a graph without drawing every edge.

The handshake result follows because every edge contributes exactly 22 to the total degree (one at each end). A consequence is that the number of vertices of odd degree is always even.

Minimum spanning tree

A tree is a connected graph with no cycles; a tree on VV vertices has exactly V−1V - 1 edges. A spanning tree of a network includes every vertex. The minimum spanning tree (MST) is the spanning tree with the smallest total edge weight, used to connect every site (towns, computers, pipes) at minimum cost.

A reliable hand method is Prim's style growth: start at any vertex, then repeatedly add the cheapest edge that connects a new vertex to the tree built so far, never forming a cycle, until all vertices are included. The result always has V−1V - 1 edges.

Shortest path

The shortest path problem asks for the route of least total weight between two vertices. For the small networks in this course you can find it by inspection: list the candidate routes from start to finish, total the weights of each, and choose the smallest. Label intermediate vertices with the least cumulative distance to reach them, working outward from the start, so you do not miss a cheaper indirect route.

Why this matters for the exams

Network terminology and these three tasks (MST, shortest path, counting results) underpin everything else in the module. Exam 1 often tests degree, the handshake result or Euler's formula directly, while Exam 2 presents a weighted network and asks for a minimum spanning tree length or a shortest route, with marks for the correct method and total.

Exam-style practice questions

Practice questions written in the style of VCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2023 VCAA1 marksA bipartite graph is typically used to display which one of the following? A. the allocation of tasks on a construction site B. the path used to visit five different construction sites C. the total distance travelled between two construction sites D. the critical path of activities to be completed in a construction project E. the minimum length of cable required to connect six construction sites
Show worked answer →

A bipartite graph has two distinct groups of vertices, with edges only running between the groups, never within a group.

This structure naturally models an allocation problem: one group is the workers and the other is the tasks, with an edge showing that a worker can do a task.

Option A, the allocation of tasks, matches this. The other options describe a path (B), a distance (C), critical path analysis (D) and a minimum spanning tree (E), none of which is a bipartite graph, so the answer is A.

2023 VCAA1 marksA graph is drawn for a country's five states, with edges representing shared borders. Euler's formula, v + f = e + 2, holds for this graph. Complete the sentence by writing the appropriate word in the box: Euler's formula holds for this graph because the graph is connected and ___.
Show worked answer →

Euler's formula v + f = e + 2 (vertices plus faces equals edges plus two) applies to a graph only when it can be drawn in the plane with no edges crossing, that is, when it is a connected planar graph.

The graph of states and shared borders can be drawn without edges crossing, so it is planar.

The word required in the box is planar. The mark is for identifying that the graph must be planar (as well as connected) for Euler's formula to hold.