Degree Sequences and Network Representations
Telstra network engineers verify fibre diagrams before deploying hardware by checking degree sequences — if the sum of degrees is odd, the model contains an error. This lesson gives you the tools to check any network instantly and represent it as an adjacency matrix for computer processing.
Practise this lesson
Three printable worksheets that build from foundations to mastery — or build your own from any module’s questions.
A network has 5 vertices with degrees 3, 2, 2, 1, 2. Can this network exist? How would you check without drawing it?
Before reading on — write your prediction and reasoning.
The degree sum theorem: the sum of all vertex degrees equals twice the number of edges. The sum is always even. Use this to instantly check if a degree sequence is valid.
Degree sequence: list of all vertex degrees in non-increasing order, e.g. {4, 3, 2, 2, 1}.
Degree sum theorem: $\sum \deg(v) = 2 \times |E|$ — sum of all degrees equals twice the number of edges.
Validity check: odd sum → impossible network. Even sum → possibly valid.
Adjacency matrix: square grid; entry [i][j] = edges between vertex i and vertex j.
Key facts
- Degree sum theorem: Σ deg = 2|E|
- Structure of an adjacency matrix
- Sum of degrees is always even
Concepts
- Why odd degree sum is impossible
- Why undirected matrix is symmetric
- How row sums relate to degrees
Skills
- Verify a degree sequence is valid
- Construct an adjacency matrix
- Draw a network from its matrix
Every edge connects two vertices. When counting degrees, we count each endpoint separately. Each edge contributes 1 to vertex A and 1 to vertex B — total contribution of 2 per edge.
Therefore: $\sum \text{deg}(v) = 2 \times |E|$
Since every term comes from multiplying by 2, the sum is always even. If you compute an odd sum, you've made an arithmetic error.
- Add all degrees. Odd result → impossible. Even result → possibly valid.
- Edges = sum ÷ 2.
{3, 3, 1}: sum = 7 (odd) → impossible — no such network can exist.
What to write in your book
- Degree sum theorem: Σ deg(v) = 2|E|. Always even.
- Odd sum → impossible. Edges = sum ÷ 2.
An adjacency matrix is a square table. Rows and columns are labelled by vertices. Entry [i][j] = number of edges between vertex i and vertex j.
Properties for undirected networks:
- Symmetric: entry [A][B] = entry [B][A] always.
- A loop at vertex X → entry [X][X] = 2.
- No edge between i and j → entry = 0.
- Row sum for vertex i = deg(i).
Example for edges A–B, A–C, B–C, B–D:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 1 |
| C | 1 | 1 | 0 | 0 |
| D | 0 | 1 | 0 | 0 |
What to write in your book
- Adjacency matrix: square, rows/cols = vertices, entries = edge count.
- Undirected → symmetric. Row sum = degree of that vertex.
- Loop at X → entry [X][X] = 2.
To construct a matrix from a network:
- Label rows and columns with vertex names (same order).
- For each pair, count edges → enter the number.
- Fill all entries including 0s.
- Check symmetry.
To draw a network from its matrix:
- Draw one vertex per row/column label.
- For non-zero entry [i][j], draw that many edges between i and j.
- Non-zero diagonal → draw loops.
What to write in your book
- Construct: label rows/cols → count edges per pair → check symmetry.
- Draw from matrix: vertex per row → edges for non-zero entries → loops for diagonal.
Worked examples · reveal each step
Degree sequence: {3, 2, 2, 1, 2}. Is this possible? How many edges?
Build the adjacency matrix for: vertices A, B, C, D with edges A–B, A–C, B–C, B–D, C–D.
Matrix entries: [A][B]=1, [A][C]=2, [B][C]=1, [B][D]=1, all others 0. Draw the network and state the degree sequence.
- Which degree sequences are possible? (a) {5,3,2,2,2} (b) {4,3,3,2} (c) {3,3,3,1}
- A network has 6 edges. What is the sum of all vertex degrees?
- Construct the adjacency matrix for: vertices P, Q, R, S with edges P–Q, P–R, Q–R, Q–S, R–S.
- Verify your matrix using row sums and the degree sum theorem.
The degree sequence {3, 2, 2, 1, 2} has sum 10 (even) — so it is possible, with 5 edges. Your initial check only needed one addition.
What changed in your understanding?
Q1. The degree sum theorem states that the sum of all vertex degrees equals:
Q2. Which degree sequence is IMPOSSIBLE for any network?
Q3. A network has 8 edges. What is the sum of all vertex degrees?
Q4. For an undirected network, the adjacency matrix is always:
Q5. In an adjacency matrix for an undirected network, the sum of row A equals:
SA 1. A network has degree sequence {4, 3, 2, 2, 1}. (a) Is this sequence possible? (b) How many edges? (2 marks)
SA 2. Construct the adjacency matrix for a network with vertices A, B, C and edges A–B, A–C, B–C, plus a loop at B. Find the degree of each vertex. (3 marks)
SA 3. A student writes a degree sequence of {5, 4, 3, 2, 2, 1, 1}. (a) Is this valid? (b) If an error is found in one vertex's degree count, which vertex is most likely to have the error, and why? (2 marks)
Answers (click to reveal)
MC 1 — C: Σ deg = 2|E|.
MC 2 — B: {3,3,1} has sum 7 (odd) → impossible.
MC 3 — D: 2×8 = 16.
MC 4 — A: Undirected adjacency matrix is always symmetric.
MC 5 — C: Row sum = degree of that vertex.
SA 1: (a) Sum=12, even, valid [1]. (b) 6 edges [1].
SA 2: Correct matrix [2]; deg(A)=2, deg(B)=4, deg(C)=2 [1].
SA 3: (a) Sum=18, even, valid [1]. (b) The degree-5 vertex [1].
Timed questions on degree sequences, degree sum theorem and adjacency matrices.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished the practice and review.