Graphs, trees and shortest path: VCE General Mathematics Unit 4 Networks and decision mathematics

What this dot point is asking

Under "Graphs and networks" the Study Design lists "the concepts, conventions and terminology of graphs including planar graphs and Euler's rule, and directed (digraphs) and networks" and "use of matrices to represent graphs, digraphs and networks and their application". Trees and spanning trees are listed under "Trees and minimum connector problems". This page covers that vocabulary and the counting results that go with it. The algorithms that use it have their own pages: Prim's algorithm for minimum spanning trees and Dijkstra's algorithm for shortest paths.

Graph fundamentals are the most reliable marks in Networks. On recent papers the degree sum and Euler's rule were answered correctly by $76\%$ to $91\%$ of students (2023 Examination 2 Question 12, 2025 Examination 2 Question 15). The misses were in adjacency matrices (2023 Examination 1 Question 37, $66\%$; 2025 Examination 2 Question 16, only $20\%$ full marks) and in vocabulary questions that ask how many statements are true (2023 Examination 1 Question 33, $56\%$).

The answer

Vertices, edges and degree

• A graph is a set of vertices (points) joined by edges (lines). Only which vertices are joined matters, not the shape or length of the lines.
• A loop joins a vertex to itself. Multiple edges join the same pair of vertices more than once. A simple graph has neither.
• The degree of a vertex, $\deg(V)$, is the number of edges that meet at it. A loop adds 2 to the degree (both ends are at that vertex). A vertex of degree 0 is isolated.
• A graph is connected if there is a route between every pair of vertices. A bridge is an edge whose removal would disconnect a connected graph; an edge that lies on a cycle is never a bridge.
• A complete graph $K_n$ has every pair of its $n$ vertices joined by one edge, so it has $\frac{n(n-1)}{2}$ edges.
• A directed graph (digraph) has arrows on its edges; a network has a number (weight) on each edge, such as a distance, time, cost or capacity.
• A bipartite graph has two groups of vertices, with edges only between the groups. It models matching and allocation problems.

The sum of degrees

Each edge has two ends and adds 1 to the degree of each end (or 2 to one vertex, for a loop). So

Two consequences: the degree sum is always even, and the number of odd-degree vertices is always even. Both are used constantly in the Eulerian-trail questions on the Euler and Hamilton page.

Planar graphs and Euler's rule

A graph is planar if it can be drawn with no edges crossing, even if the drawing you are given has crossings (redraw an edge around the outside to check). A planar drawing divides the plane into faces: the regions bounded by edges, plus the outer region.

For any connected planar graph,

where $v$ is the number of vertices, $f$ the number of faces and $e$ the number of edges. The rule fails for disconnected graphs and cannot be applied to non-planar graphs (such as $K_5$), which is why "connected and planar" is the answer to "why does Euler's rule hold" (2023 Examination 2 Question 12b, $81\%$).

Adjacency matrices

The adjacency matrix of a graph with $n$ vertices is an $n \times n$ matrix whose element in row $i$, column $j$ is the number of edges joining vertex $i$ to vertex $j$.

• For an undirected graph it is symmetric.
• Multiple edges give elements greater than 1.
• VCAA records a loop as 1 on the leading diagonal, but a loop adds 2 to the degree. So the degree of a vertex is its row total plus the number of loops at it.
• For a graph with no loops, the sum of all elements is $2e$, so $e = \frac{\text{sum of elements}}{2}$.
• For a digraph, the element in row $i$, column $j$ counts the arrows from $i$ to $j$, and the matrix need not be symmetric (communication and dominance matrices are examples).

2025 Examination 2 Question 16 gave a map of passages between five areas of a gym and an adjacency matrix with three unknown elements, including 1s on the leading diagonal for passages that lead from an area back to itself. The answer was $x = 2$, $y = 4$, $z = 2$; only $20\%$ got all three, and $y$ was often given as 3. Count every separate route between two areas that does not pass through another area.

Trees and spanning trees

A tree is a connected graph with no cycles. Every tree with $v$ vertices has exactly $v - 1$ edges, every edge of a tree is a bridge, and a tree is planar with only one face (so $v + 1 = (v - 1) + 2$).

A spanning tree of a connected graph is a tree that includes every vertex of the graph, using only edges of the graph. A graph usually has many spanning trees. To draw one, keep adding edges from the original graph that reach a new vertex, until all $v$ vertices are joined by $v - 1$ edges.

In a weighted network, a minimum spanning tree is a spanning tree of least total weight: the cheapest way to connect every vertex (a minimal connector problem). Find it by inspection or by Prim's algorithm (start anywhere, repeatedly add the cheapest edge that reaches a new vertex). The shortest path between two vertices is a different problem: the cheapest route from one vertex to another, found by inspection or Dijkstra's algorithm.

Where these ideas lead

Every Networks topic uses this vocabulary. Degrees decide Eulerian trails and circuits; trees and spanning trees lead to Prim's algorithm; weighted networks lead to shortest paths (Dijkstra's algorithm) and flow problems; bipartite graphs lead to allocation with the Hungarian algorithm; and digraphs with arrows between tasks lead to critical path analysis. Adjacency matrices connect the Networks area of study to the Matrices area, where communication and dominance matrices are the adjacency matrices of digraphs.