What is a non-symmetric matrix for an undirected graph?

Undirected graphs must give symmetric matrices; an asymmetric matrix means you have missed an entry.

§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How do we describe a graph precisely and record it as a matrix?

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

How to use the core graph vocabulary of vertices, edges, degree, loops and multiple edges, apply the handshake rule, and translate between a graph and its adjacency matrix.

Generated by Claude Opus 4.87 min answerUpdated 2026-06-02

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

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

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

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

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.

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.

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.

Exam-style practice questions

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

WACE 20225 marksA 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 20244 marksExplain 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.