Graph terminology and adjacency matrices in WACE Mathematics Applications Unit 3

Syllabus dot point

“Use vertex, edge, degree, loop and multiple-edge terminology, apply the handshake rule, and represent a graph with an adjacency matrix.”

WACEMathematics ApplicationsUnit 37 min readUpdated 2 Jun 2026

Quick answer

A graph is a set of vertices joined by edges. The degree of a vertex is the number of edge-ends meeting it, with a loop counting twice. The handshake rule says the degrees sum to twice the number of edges. An adjacency matrix records how many edges join each pair of vertices; for an undirected graph it is symmetric, and loops appear as $2$ on the leading diagonal.

Jump to a section

What this dot point is asking
The vocabulary
The handshake rule
The adjacency matrix
Reading a matrix back into a graph
Exam-style questions

What this dot point is asking

You must use the core vocabulary correctly, apply the handshake rule, and translate both ways between a graph and its adjacency matrix.

The vocabulary

Core graph terms

A vertex (node) is a point. An edge joins two vertices. The degree of a vertex is the number of edge-ends meeting it. A loop is an edge joining a vertex to itself and adds $2$ to that vertex's degree. Multiple edges are two or more edges between the same pair of vertices. A simple graph has no loops and no multiple edges.

Other terms appear throughout networks: a graph is connected if you can reach every vertex from every other; a subgraph uses some of the vertices and edges; a complete graph joins every pair of vertices exactly once.

The handshake rule

Each edge contributes one edge-end to each of its two vertices, so it adds $2$ to the total degree count. This gives a checking rule used constantly.

The handshake rule

$\displaystyle \sum (\text{degrees}) = 2 \times (\text{number of edges})$ .

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

Use it to check your degree count or to find a missing degree. If five of six vertices have degrees $3, 3, 4, 2, 2$ and the graph has $9$ edges, the degrees must sum to $18$ , so the sixth vertex has degree $18 - 14 = 4$ .

The adjacency matrix

An adjacency matrix is a square array with one row and one column per vertex. The entry in row $i$ , column $j$ is the number of edges joining vertex $i$ to vertex $j$ .

For an undirected graph the matrix is symmetric: entry $(i,j)$ equals entry $(j,i)$ .
A loop contributes $2$ to the diagonal entry for that vertex (it joins the vertex to itself with two edge-ends).
Multiple edges show as entries greater than $1$ .
The degree of a vertex is the sum of its row (counting a diagonal loop entry as is, since it already counts $2$ ).

Worked example

Building an adjacency matrix

A network has vertices $P, Q, R, S$ with edges $PQ$ , $PR$ , $QR$ , $QS$ , two edges between $R$ and $S$ , and a loop at $P$ .

Step 1: List what each vertex connects to

Before filling the matrix, it helps to record each vertex's neighbours explicitly so nothing is missed. $P$ joins $Q$ (once), $R$ (once), and itself (loop). $Q$ joins $P$ , $R$ , $S$ . $R$ joins $P$ , $Q$ , $S$ (twice). $S$ joins $Q$ , $R$ (twice).

Step 2: Fill the matrix in order P, Q, R, S

Each off-diagonal entry counts the edges between that pair; a loop at a vertex goes on the diagonal as $2$ because it contributes two edge-ends to the same vertex. Row $P = (2, 1, 1, 0)$ : the loop gives a diagonal $2$ .

Row $Q = (1, 0, 1, 1)$ .

Row $R = (1, 1, 0, 2)$ : the double edge $RS$ gives the entry $2$ .

Row $S = (0, 1, 2, 0)$ .

Step 3: Check symmetry and degrees

An undirected graph always produces a symmetric matrix, so checking that entry $(i,j)$ equals entry $(j,i)$ throughout catches transcription errors. The matrix is symmetric (the graph is undirected). Degrees from row sums: $\deg(P) = 4$ , $\deg(Q) = 3$ , $\deg(R) = 4$ , $\deg(S) = 3$ , summing to $14 = 2 \times 7$ edges (counting the loop as one edge and the double edge as two), confirming the handshake rule.

Reading a matrix back into a graph

Given a matrix, reverse the process: each off-diagonal entry tells you how many edges join those two vertices, and a diagonal entry of $2$ marks a loop. The matrix is the compact, calculator-friendly way to store a network, which is why SCSA uses it for the matrix-power method of counting walks between vertices.

Powers of the adjacency matrix count walks

The $(i,j)$ entry of the matrix raised to the power $k$ gives the number of walks of length exactly $k$ from vertex $i$ to vertex $j$ . Squaring the matrix counts two-step connections, a result SCSA sometimes asks you to interpret.

In a transport network this is useful: if the matrix records direct flights between cities, the squared matrix gives the number of one-stopover (two-flight) routes between each pair, and the sum of a matrix and its square counts routes of up to two legs. Interpreting such an entry in context (for example, "there are three two-flight routes from city $A$ to city $D$ ") is a standard application of matrix powers to graphs.

Common errors

Counting a loop as degree 1: A loop adds $2$ to the degree and appears as $2$ on the diagonal.
A non-symmetric matrix for an undirected graph: Undirected graphs must give symmetric matrices; an asymmetric matrix means you have missed an entry.
Confusing rows and columns for directed graphs: In a directed graph the entry $(i,j)$ counts edges from $i$ to $j$ , and the matrix need not be symmetric.
Miscounting edges with multiple edges or loops: Apply the handshake rule as a check; if the degree sum is odd, you have made an error.

Exam-style questions

Questions in the style of SCSA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

WACE 2022-style5 marks

A graph has vertices

A

B

C

D

with edges

AB

AC

BC

BD

CD

and a loop at

A

. (a) State the degree of each vertex. (b) Verify the handshake rule. (c) Write the adjacency matrix.

Show worked answer →

Count edge-ends at each vertex; a loop adds $2$ to its vertex's degree.

(a) $\deg(A) = 1 + 1 + 2 = 4$ (edges $AB$ , $AC$ and the loop), $\deg(B) = 3$ ( $AB$ , $BC$ , $BD$ ), $\deg(C) = 3$ ( $AC$ , $BC$ , $CD$ ), $\deg(D) = 2$ ( $BD$ , $CD$ ). (2 marks)

(b) Sum of degrees $= 4 + 3 + 3 + 2 = 12 = 2 \times 6$ edges (the loop counts as one edge), so the handshake rule holds. (1 mark)

(c) Order $A, B, C, D$ . With the loop at $A$ entered as $2$ on the leading diagonal: row $A = (2,1,1,0)$ , row $B = (1,0,1,1)$ , row $C = (1,1,0,1)$ , row $D = (0,1,1,0)$ . (2 marks)

Markers reward the loop contributing $2$ to both degree and the diagonal entry, and a symmetric matrix for an undirected graph.

WACE 2024-style4 marks

Explain the difference between a simple graph and a graph that is not simple, then state what feature of an adjacency matrix shows that a graph is undirected.

Show worked answer →

A simple graph has no loops and no multiple edges between the same pair of vertices.

A graph that is not simple contains at least one loop (an edge joining a vertex to itself) or multiple edges (two or more edges between the same pair of vertices). (2 marks)

An undirected graph has a symmetric adjacency matrix: the entry in row $i$ , column $j$ equals the entry in row $j$ , column $i$ , because each edge is counted in both directions. (2 marks)

Markers reward the loop-and-multiple-edge definition and the symmetry of the matrix for undirected graphs.

Graph terminology and adjacency matrices in WACE Mathematics Applications Unit 3

What this dot point is asking

The vocabulary

The handshake rule

The adjacency matrix

Building an adjacency matrix

Step 1: List what each vertex connects to

Step 2: Fill the matrix in order P, Q, R, S

Step 3: Check symmetry and degrees

Reading a matrix back into a graph

Exam-style questions

Practise this

Sources & how we know this