QLDGeneral MathematicsSyllabus dot point

Topic 2: Graphs and networks - how do we represent and analyse connections using vertices and edges?

Represent a situation as a graph or network using vertices and edges, determine the degree of vertices and verify the handshaking result, classify graphs as connected, simple, complete, bipartite or planar, apply Euler's formula, and identify Eulerian and Hamiltonian trails and circuits

A focused answer to the QCE General Mathematics Unit 4 dot point on graphs and networks. Covers vertices, edges and degree, the handshaking lemma, types of graphs, Euler's formula for planar graphs, and Eulerian versus Hamiltonian trails and circuits, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

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

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

What this dot point is asking

QCAA wants you to model connections (roads, friendships, pipes, tasks) as a graph of vertices joined by edges, then describe and classify that graph and reason about routes through it. You count degrees, verify the handshaking result, name the graph type, apply Euler's formula to planar graphs, and decide whether the graph has an Eulerian or Hamiltonian trail or circuit. This is the foundation of Unit 4 Topic 2 and sets up the shortest-path, spanning-tree and flow work that follows.

The answer

Vertices, edges and degree

A graph consists of vertices (nodes) joined by edges (lines). The degree of a vertex is the number of edge-ends meeting at it; a loop counts twice. The handshaking result states that the sum of all degrees equals twice the number of edges:

\sum \deg(v) = 2E.

A direct consequence is that the number of odd-degree vertices is always even.

Classifying graphs

Connected. There is a path between every pair of vertices.
Simple. No loops and no multiple edges between the same pair.
Complete. Every pair of vertices is joined by exactly one edge; the complete graph on $n$ vertices has $\dfrac{n(n-1)}{2}$ edges.
Bipartite. Vertices split into two groups with edges only between groups, never within.
Planar. Can be drawn so that no edges cross.

Euler's formula for planar graphs

For any connected planar graph,

V - E + F = 2,

where $V$ is vertices, $E$ is edges and $F$ is faces (regions, including the unbounded outer region). This lets you find any one of the three counts from the other two.

Eulerian and Hamiltonian routes

An Eulerian trail uses every edge exactly once. It exists if and only if the graph is connected and has exactly $0$ or $2$ vertices of odd degree. With exactly $0$ odd vertices the trail closes into an Eulerian circuit.
A Hamiltonian path visits every vertex exactly once. If it returns to the start it is a Hamiltonian cycle. There is no simple degree test for these; you reason case by case.

The mnemonic: Eulerian is about edges, Hamiltonian is about vertices.

Worked example

Handshaking, Euler's formula and trail tests

A connected planar graph has $6$ vertices with degrees $2, 2, 3, 3, 4, 4$ .

Step 1: Apply the handshaking result to find the number of edges.

\sum \deg(v) = 2 + 2 + 3 + 3 + 4 + 4 = 18, \qquad E = \frac{18}{2} = 9.

Verify: $2+2+3+3+4+4 = 18$ and $18 / 2 = 9$ . There are $9$ edges.

Step 2: Use Euler's formula to find the number of faces.

V - E + F = 2 \implies 6 - 9 + F = 2 \implies F = 2 + 3 = 5.

Verify: $6 - 9 = -3$ , and $-3 + 5 = 2$ . There are $5$ faces.

Step 3: Test for an Eulerian trail or circuit. Count odd-degree vertices: the degrees $3$ and $3$ are odd, so there are exactly $2$ odd vertices.

Because the graph is connected with exactly $2$ odd-degree vertices, it has an Eulerian trail (every edge once) but not an Eulerian circuit. The trail must start at one odd-degree vertex and finish at the other.

Exam-style practice questions

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

2022 QCAA5 marksThe paths connecting various landmarks in a park are shown, with vertices Bus stop (B), Coffee shop (C), Duck pond (D), Playground (P), Rose garden (R) and Water feature (W). a) Identify one cycle that passes through the rose garden and the playground. [1 mark] b) Identify whether the graph is Eulerian or semi-Eulerian. Justify your response. [2 marks] c) Construct an adjacency matrix from the graph, using the vertex order listed in the key (B, C, D, P, R, W). [2 marks]

Show worked answer →

a) Cycle (1 mark). Any closed walk that starts and ends at the same vertex, uses no repeated edges, and includes both R and P works. The sample answer is R - W - P - D - R, written RWPDR.

b) Eulerian or semi-Eulerian (2 marks). Count the degree of every vertex. The graph has exactly two vertices of odd degree and the rest even, so it is semi-Eulerian (1 mark for the classification, 1 mark for the justification). The rule: a connected graph is Eulerian (has an Eulerian circuit) when every vertex is even, and semi-Eulerian (has an Eulerian trail but not a circuit) when exactly two vertices are odd.

c) Adjacency matrix (2 marks). Label the rows and columns in the same order B, C, D, P, R, W (1 mark for matching labels on both axes). Each entry is the number of edges directly joining that pair of vertices; multiple paths between the same two landmarks give an entry of 2, and the diagonal is 0 with no loops (1 mark for correct entries).

The key skills are reading degrees off the diagram to classify the graph, and being consistent with the vertex order in the adjacency matrix so it is symmetric for an undirected graph.