QCE General Mathematics - Unit 4 - Graphs and networks
Graphs, Terminology and Adjacency Matrices | QCE General Mathematics
Learn graph terminology, directed and weighted networks, and adjacency matrices for QCE General Mathematics.
Updated 2026-05-18 - 5 min read
QCAA official coverage - General Mathematics 2025 v1.3
Exact syllabus points covered
- Understand the meaning of 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 practical situations, e.g. tracks connecting camp sites in a national park, a social network, a transport network with one-way streets, the results of a round-robin sporting competition.
- Construct an adjacency matrix from a given graph or digraph.
- Construct a graph or digraph from a given adjacency matrix.
In decision mathematics, a graph is a set of vertices joined by edges. A network is a graph used to model a real situation, such as roads, friendships, pipes, flights or tasks.
Original Sylligence diagram for general network terminology.
Core terminology
| Term | Meaning | |---|---| | Vertex or node | a point in the graph | | Edge or arc | a connection between vertices | | Loop | an edge from a vertex to itself | | Degree | number of edges incident with a vertex | | Simple graph | no loops and no multiple edges | | Complete graph | every pair of vertices is connected | | Weighted graph | edges have values such as distance or cost | | Directed graph | edges have direction |
Adjacency matrices
An adjacency matrix records how vertices are connected. For an undirected graph, the matrix is symmetric. For a directed graph, the entry in row $A$, column $B$ counts arcs from $A$ to $B$.
| | A | B | C | |---|---:|---:|---:| | A | 0 | 1 | 1 | | B | 1 | 0 | 0 | | C | 1 | 0 | 0 |
This matrix shows that $A$ is connected to $B$ and $C$, but $B$ and $C$ are not connected to each other.
Worked example
More graph types and degree details
A loop contributes $2$ to the degree of a vertex in many graph-theory conventions, but some school contexts describe it carefully as a special edge attached to the same vertex. Follow the convention used in the question.
| Graph type | Key feature | |---|---| | Complete graph | every pair of vertices is joined | | Bipartite graph | vertices split into two sets, with edges only between sets | | Directed graph | edges have direction | | Weighted graph | edges have numerical values | | Subgraph | uses some of the vertices and edges of a larger graph |
Matrix interpretation
For an undirected graph, the adjacency matrix is symmetric because a connection from $A$ to $B$ also connects $B$ to $A$. For a digraph, symmetry is not guaranteed.
Powers of adjacency matrices can count routes of a given length in some network contexts. For example, an entry in $A^2$ can represent the number of two-edge walks between two vertices. If this appears, read the question carefully because the interpretation depends on the network.
Constructing a network from a matrix
Work systematically:
- Label the vertices in the matrix order.
- Read across each row.
- Draw the listed connections to the column vertices.
- For a digraph, include arrow direction.
- For an undirected graph, avoid drawing each edge twice.
Depth: graph terminology table
Graph questions become much easier when the vocabulary is precise.
| Term | Meaning | |---|---| | vertex | a point or node | | edge | a connection between two vertices | | loop | an edge from a vertex to itself | | multiple edges | more than one edge connecting the same two vertices | | degree | number of edge ends meeting a vertex | | simple graph | no loops and no multiple edges | | connected graph | every vertex can be reached from every other vertex | | subgraph | part of a graph using some vertices and edges |
For a loop, the degree contribution is $2$ because both ends of the edge meet the same vertex.
Adjacency matrices
An adjacency matrix records how many edges connect each pair of vertices. For an undirected graph, the matrix is symmetric because the connection from A to B is the same as the connection from B to A.
Reading paths from matrix powers
Matrix powers can count walks. If $A$ is an adjacency matrix, then entries in $A^2$ count the number of two-edge walks between vertices. Entries in $A^3$ count three-edge walks.
This is useful because it turns a network question into a structured table. However, a walk can repeat vertices and edges, so it is not always the same as a path or cycle.
Building a graph from a matrix
Use this workflow:
- Label the vertices in the matrix order.
- Check diagonal entries for loops.
- For an undirected graph, use only one triangle of the matrix to avoid double-counting.
- Draw each edge count shown by the matrix.
- Check degrees against row sums.