Graphs, networks and adjacency matrices (QCE General Mathematics Unit 4)

What this dot point is asking

A graph is a way of drawing connections: towns joined by roads, people joined by friendships, camp sites joined by tracks, players joined by the matches they played. The QCAA General Mathematics 2025 syllabus opens Topic 3 (Graphs and networks) with the sub-topic "Graphs, associated terminology and the adjacency matrix". You must:

• understand and use the terms graph, vertex (node), edge (arc), loop, degree of a vertex, subgraph, simple graph, complete graph, bipartite graph, directed graph (digraph), weighted graph and network;
• construct a network diagram to represent a practical situation, such as tracks between camp sites, a social network, one-way streets or the results of a round-robin competition;
• construct an adjacency matrix from a graph or digraph, and construct a graph or digraph from an adjacency matrix.

This vocabulary is used in every later networks question (planar graphs, Eulerian and Hamiltonian routes, spanning trees, critical paths, flow and assignment), so precise use of the terms earns marks throughout Unit 4.

The answer

Vertices, edges, loops and degree

A graph consists of vertices (also called nodes), drawn as dots, and edges (also called arcs), drawn as lines joining pairs of vertices. The position and length of the lines do not matter: only which vertices are joined.

• A loop is an edge that starts and finishes at the same vertex.
• Multiple edges are two or more edges joining the same pair of vertices (for example, two different roads between the same two towns).
• The degree of a vertex is the number of edge ends at that vertex. A loop has both of its ends at the vertex, so it adds 2 to the degree.

Every edge has two ends, so adding up all the degrees counts every edge twice:

Because $2e$ is even, the number of vertices with odd degree is always even. This gives quick checks: a graph with degrees 1, 2, 3, 3, 4, 4, 4 is impossible (the sum, 21, is odd).

Types of graphs

Some words are used both loosely and precisely. In everyday use "network" means any system of connections; in the syllabus a network is a weighted graph. A complete graph on $n$ vertices has every vertex of degree $n - 1$ and $\frac{n(n-1)}{2}$ edges: for 6 vertices, $\frac{6 \times 5}{2} = 15$.

Constructing network diagrams

To turn a practical situation into a graph:

1. Decide what the vertices are (the places, people, teams or tasks).
2. Decide what an edge means (a road, a friendship, a match, a result, a dependency).
3. Decide whether direction matters. One-way streets, "beat" relationships and task order need a digraph.
4. Decide whether edges need weights (distance, time, cost, capacity). If so, it is a network.
5. Draw it neatly, labelling every vertex (and every weight), avoiding unnecessary crossings.

For example, camp sites A to E joined by walking tracks A-B 4 km, A-C 3 km, B-C 2 km, B-D 5 km, C-E 6 km and D-E 3 km form an undirected, weighted graph (a network) with 5 vertices and 6 edges.

The adjacency matrix

An adjacency matrix records a graph as a square table of numbers. With the vertices listed in the same order along the rows and the columns, the entry in row X and column Y is the number of edges joining X to Y.

Reading and writing the matrix:

• Undirected graphs give symmetric matrices: an edge between A and C is counted in row A, column C and row C, column A.
• Multiple edges show as numbers greater than 1 (the 2s above).
• Loops appear on the leading diagonal. A loop is usually entered as 1 (one edge joins the vertex to itself), even though it adds 2 to the degree. Follow the convention given in the question if it states one.
• For a simple graph with no loops, the diagonal is all zeros, every entry is 0 or 1, and each row sum is the degree of that vertex.

To draw a graph from a matrix, place a vertex for each row, then for each entry above the leading diagonal draw that many edges between the row vertex and the column vertex, and draw a loop for each diagonal entry. Counting edges from a symmetric matrix: add the entries above the diagonal, then add the diagonal entries (loops).

Adjacency matrices of digraphs

For a digraph, the entry in row X and column Y is the number of edges directed from X to Y. The matrix is generally not symmetric. In a round-robin competition where an arrow runs from the winner to the loser, the row sums give each player's number of wins and the column sums give losses.

Round robin among P, Q, R and S: P beat Q and R; Q beat R; R beat S; S beat P and Q.

Row sums: P 2, Q 1, R 1, S 2. Column sums (losses): P 1, Q 2, R 2, S 1.

Where this leads

The same graph language feeds every later sub-topic in Unit 4:

• Planar graphs and Euler's formula $v + f - e = 2$ (see the planar graphs page).
• Walks, trails, paths and Eulerian or Hamiltonian routes, decided using the degrees you calculate here (see the Eulerian and Hamiltonian page).
• Shortest paths and minimum spanning trees in weighted graphs.
• Critical path analysis on directed activity networks, flow networks on directed weighted graphs, and assignment problems on bipartite graphs.