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 onwrite 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.
Degree sum theorem: every edge contributes 1 to two different vertices, so the total of all degrees = 2 × edges. Corollary: the number of odd-degree vertices is always even. This is used to check whether an Eulerian circuit or trail is possible.
Pause, copy the degree sum theorem (sum of all degrees = 2 × edges; always even) and its corollary (the number of odd-degree vertices in any network is always even, this lets you verify a degree sequence is possible) into your book.
We just saw the degree sum theorem, every edge contributes 1 to two vertices, so total degrees = 2 × edges, and the number of odd-degree vertices is always even. That raises a question: the degree sequence gives numbers for each vertex, but it doesn't show which vertices are actually connected to each other, is there a way to represent all connections in a grid format? This card answers it → an adjacency matrix is an n × n grid where entry [i][j] = the number of edges between vertex i and vertex j, capturing the full connection structure.
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 |
Adjacency matrix: n×n table where entry [i][j] = number of edges between vertices i and j. For undirected networks: matrix is symmetric (entry [i][j] = entry [j][i]). Loops appear on the diagonal. Row sums = vertex degrees.
Pause, copy the adjacency matrix construction rules: n × n table; entry [i][j] = number of edges between vertex i and vertex j; diagonal entry = twice the number of loops; for undirected networks the matrix is symmetric ([i][j] = [j][i]); row sum = degree of that vertex into your book.
We just saw the structure of an adjacency matrix and that it is symmetric for undirected networks (entry [i][j] = entry [j][i]). That raises a question: what changes when the network is directed, and how do you read a given matrix to find the number of edges between two specific vertices? This card answers it → for directed networks the matrix is not symmetric; entry [i][j] counts arrows from vertex i to vertex j, while [j][i] counts arrows from j to i, these can differ.
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.
To read a matrix: entry [i][j] = edges from row-vertex to column-vertex. To construct: label rows and columns with the same vertex list; count edges between each pair. For directed networks, [i][j] ≠ [j][i] in general, the matrix is not symmetric.
Pause, copy the matrix reading rule (entry [i][j] = edges from row-vertex i to column-vertex j) and the directed-vs-undirected symmetry distinction (undirected: [i][j] = [j][i]; directed: [i][j] and [j][i] can differ because arrows are one-way) into your book.
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.