The vocabulary of networks. Every other Networks topic, Euler paths, minimum spanning trees, shortest path, uses these ideas. Get the basics right and everything else clicks into place.
What even is this?
A graph is a collection of dots (vertices) connected by lines (edges). That's literally it. They're used to model road networks, social connections, project schedules, power grids, anything where things connect to other things.
This page gives you the key terms and rules you need before anything else in Networks makes sense. Learn these first.
If you only do one thing
A graph is dots (vertices) joined by lines (edges). Degree = how many edges touch a vertex. Most questions start right there.
The 10-minute version
Low energy? Do just this and you have still won the day. Zero is the only fail.
The one move: read the first formula box and the first worked example above, then do Practice Question 1. Screenshot the win for Nat and stop there.
4 words unlock this whole page
Vertexa dot in the network
Degreehow many edges touch a vertex
Edgea line connecting two vertices
Weighta number on an edge (distance, cost, time)
Everything else on this page (digraph, tree, handshaking lemma...) is just these four ideas
combined or named differently. If those four stick, the rest follows.
A point or node in the graph. Drawn as a dot, usually labelled with a letter.
Real world: towns, computers, junctions, people
Edge
A line connecting two vertices. Represents a connection or relationship between them.
Real world: roads, cables, friendships, pipelines
Edges: A, B, A, C, B, C, B, D, C, D | Degree labels in gold
2
Degree of a Vertex
The degree of a vertex is the number of edges connected to it. Count the lines attached to each dot.
Vertex
Connected to
Degree
A
B, C
2
B
A, C, D
3
C
A, B, D
3
D
B, C
2
Total (sum of all degrees)
10
Handshaking Lemma
Sum of all degrees = 2 × (number of edges)
Why? Every edge connects exactly two vertices, so each edge contributes exactly 2 to the total degree sum. If the graph has e edges, the sum of degrees = 2e.
In our example: 2 + 3 + 3 + 2 = 10 = 2 × 5 ✓
Odd and even degrees matter. The number of vertices with odd degree determines whether a graph is traversable (this comes up in Euler Paths, next topic).
3
Types of Graphs
Simple Graph
No loops (edge from a vertex to itself) and no parallel edges (two edges between the same pair). The default type.
Used for: most network problems in this course
Directed Graph (Digraph)
Edges have arrows, you can only travel in the direction shown. A→B does not mean you can go B→A.
Used for: one-way streets, activity networks, workflows
Weighted Graph
Each edge has a number (weight) showing distance, time or cost. Most practical graph problems use weights.
Used for: MST, shortest path, critical path analysis
Connected Graph
Every vertex can be reached from every other, the graph is in one piece. A disconnected graph has isolated clusters.
Required for: spanning trees, Euler circuits
4
Trees
A tree is a connected graph with no cycles. It's the most efficient way to connect all nodes, no redundant connections.
Tree Formula
A tree with n vertices has exactly n − 1 edges
Why n − 1? Start with 1 vertex and 0 edges. Each time you add a new vertex, you connect it with exactly 1 new edge (to keep it connected without creating a cycle). After adding n − 1 more vertices you have n vertices and n − 1 edges.
A tree with 6 vertices must have exactly 5 edges, and no cycles
5
Adjacency Matrices
An adjacency matrix is a graph written as a table. Each cell shows how many edges join that row's vertex to that column's vertex. Exams love asking you to build the matrix from a picture, or draw the graph from a matrix, it's the same information in two costumes.
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
0
1
D
0
1
1
0
Three things to check every time: 1. It's symmetric. If A joins B, then B joins A, so the matrix mirrors across the diagonal (for undirected graphs). 2. Row totals give degrees. Add up row B: 1 + 0 + 1 + 1 = 3 = the degree of B. Instant self-check against the handshaking lemma. 3. The diagonal shows loops. A number in row B, column B means B has an edge to itself. All zeros on the diagonal = no loops.
Exam move: "Use an adjacency matrix to represent..." means build the table from the situation (the QCAA sample asks this with a map of Australia's state borders). Work through the vertices in order, one row at a time, and count shared borders/edges. Then check the symmetry, if row QLD column NSW is 1, row NSW column QLD must be 1 too.
A cell can hold a number bigger than 1: two parallel edges between C and D would make that cell a 2. A whole row of zeros means that vertex is isolated, connected to nothing.
6
Worked Examples
📐
Example A · Degrees and the Handshaking Lemma
A graph has vertices P, Q, R, S, T with edges PQ, PR, QR, QS, RS, ST. Find the degree of each vertex and verify the handshaking lemma.
1
Count edges at each vertex
P connects to: Q, R → degree 2
Q connects to: P, R, S → degree 3
R connects to: P, Q, S → degree 3
S connects to: Q, R, T → degree 3
T connects to: S → degree 1
2
Verify the lemma
Sum of degrees = 2 + 3 + 3 + 3 + 1 = 12
Number of edges = 6 → 2 × 6 = 12 ✓
Which type of graph should you use to model a one-way road network? Explain why.
Tap to reveal ▾
A directed graph (digraph), because the arrows show which direction travel is allowed. In an undirected graph, every edge can be used in both directions, but one-way roads can only be used in one direction.
5
A network has 7 vertices. Every vertex has the same degree and the sum of all degrees is 28. What is the degree of each vertex, and how many edges are in the network?
Tap to reveal ▾
Each vertex degree = 28 ÷ 7 = 4
Number of edges = 28 ÷ 2 = 14 edges
6
Using the adjacency matrix in Section 5: which vertices are adjacent to C? What is the degree of A? Are there any loops?
Tap to reveal ▾
Read row C: 1s under A, B and D → C is adjacent to A, B and D.
Add row A: 0 + 1 + 1 + 0 = degree 2.
The diagonal is all zeros → no loops.