Networks
A network is a set of vertices joined by edges, and the degree of a vertex is the number of edges that meet there. This NSW Year 9 Advanced maths subtopic introduces networks and the routes through them (NESA outcome MA5‑NET‑P‑01).
You will count edges and degrees, use the fact that the degrees add to twice the number of edges, and name a route as a walk, trail, path, circuit or cycle. You will decide from its odd vertices whether a network has an Eulerian trail or circuit, plan a jogger's route through a park, and find how many new bridges would solve the Seven Bridges of Koenigsberg problem. It is part of Year 9 Advanced Properties of Geometric Figures.
Theory
A network (or graph) is a set of vertices joined by edges. This Year 9 Advanced maths page covers the degree of a vertex, the handshake rule, the five kinds of route (walk, trail, path, circuit, cycle), and how odd vertices decide whether a network has an Eulerian trail or Eulerian circuit. Networks lead on to Mathematics Standard.
A network or graph is a collection of vertices (dots) joined by edges (lines). It can model roads between towns, friendships, pipes or flights. The same network can be drawn in many ways: only which vertices are joined matters, not the lengths or shapes of the edges.
The degree of a vertex is the number of edge-ends at it. Two edges between the same pair of vertices each count, so a double edge adds \(2\). A network is connected if there is a route between every pair of vertices.
A walk is any route along edges. A trail is a walk that never repeats an edge. A path is a walk that never repeats a vertex. A circuit is a trail that finishes where it started, and a cycle is a path that finishes where it started. Every path is a trail, but a trail may pass through a vertex twice.
An Eulerian trail uses every edge exactly once. An Eulerian circuit is an Eulerian trail that ends where it started. Euler invented this idea in 1736 to show that no walk crosses each of the Seven Bridges of Königsberg exactly once.
Handshake rule. Every edge has two ends, so:
| Connected network with | Result |
|---|---|
| \(0\) odd vertices | Eulerian circuit: start anywhere, finish at the same vertex |
| exactly \(2\) odd vertices | Eulerian trail (not a circuit): start at one odd vertex, finish at the other |
| \(4, 6, 8, \ldots\) odd vertices | no Eulerian trail |
How to analyse a network
- Degrees: count the edge-ends at every vertex. Check the total is \(2 \times\) the number of edges.
- Odd vertices: count them. That number decides the Eulerian question (see the Formulas table), as long as the network is connected.
- Find the trail: start at an odd vertex (any vertex if all are even), cross off each edge as you use it, and avoid using an edge that would cut you off from edges not yet used.
- Naming a route: list its edges and its vertices. Repeated edge: walk. Repeated vertex: trail or circuit. No repeats: path or cycle.
Using the handshake rule backwards
- Edges from degrees: add the degrees and halve.
- A missing degree: write the degree sum in two ways (from the vertices and as \(2 \times\) edges), set them equal and solve.
- Adding edges: a new edge adds \(1\) to the degree of each of its two ends, so it can make at most two odd vertices even.
(i) find the degree of each vertex
(ii) check your answers with the handshake rule
(iii) list the vertices of odd degree.
(i) Count edge-ends at each vertex. \(S\) and \(T\) are joined by two edges, so each of those counts.
| \(\deg P = 2,\ \deg Q\) | \(=\) | \(3,\ \deg R = 3\) |
| \(\deg S = 4,\ \deg T\) | \(=\) | \(3,\ \deg U = 1\) |
(ii) There are \(8\) edges, so the degrees should add to \(2 \times 8 = 16\).
| \(2 + 3 + 3 + 4 + 3 + 1\) | \(=\) | \(16 = 2 \times 8\) |
(iii) The odd-degree vertices are \(\boldsymbol{Q, R, T}\) and \(\boldsymbol{U}\). There are four of them: odd vertices always come in pairs.
(i) \(P - Q - S - R - P\)
(ii) \(Q - R - S - Q - P\)
(iii) \(P - R - S - R - Q\).
(i) Edges \(PQ, QS, SR, RP\): none repeated. No vertex is repeated except the start, and it finishes where it began. A closed path is a cycle.
(ii) Edges \(QR, RS, SQ, QP\): none repeated, so it is at least a trail. \(Q\) is visited a second time, so it is not a path. It does not finish at \(Q\), so it is a trail.
(iii) Edges \(PR, RS, SR, RQ\): the edge \(RS\) is used twice. It is only a walk.
(i) Does it have an Eulerian circuit, an Eulerian trail or neither?
(ii) Write down an Eulerian trail if there is one.
(iii) Which one new edge would give it an Eulerian circuit?
(i) The degrees (in orange) are \(A: 2,\ B: 4,\ C: 4,\ D: 3,\ E: 3\). The network is connected and has exactly two odd vertices, \(D\) and \(E\). So it has an Eulerian trail but no Eulerian circuit.
(ii) The trail must start at one odd vertex and finish at the other:
It uses all \(8\) edges once each.
(iii) A second edge between \(D\) and \(E\) adds \(1\) to each of their degrees, making every degree even. Then an Eulerian circuit exists.
The sum of the degrees is twice the number of edges.
| \(2 + 3 + 3 + x + 5 + 5\) | \(=\) | \(2 \times 11\) |
| \(18 + x\) | \(=\) | \(22\) |
| \(x\) | \(=\) | \(\mathbf{4}\) |
The odd degrees are \(3, 3, 5, 5\): four odd vertices. An Eulerian trail needs \(0\) or \(2\), so this network has no Eulerian trail.
One network that fits the degrees is shown below.
Common pitfalls
Frequently asked questions
What is the degree of a vertex?
It is the number of edges that meet at the vertex, counting each edge-end. If two edges join the same two vertices, both count, and a vertex with no edges has degree 0.
What is the handshake rule?
The sum of the degrees of all the vertices equals twice the number of edges, because every edge has two ends. A network with 9 edges has a degree sum of 18.
What is the difference between a trail and a path?
A trail never uses the same edge twice but may visit a vertex more than once. A path never visits the same vertex twice, so it can never repeat an edge either. Every path is a trail.
How do you know if a network has an Eulerian circuit?
A connected network has an Eulerian circuit when every vertex has even degree. If exactly two vertices have odd degree, it has an Eulerian trail that starts at one and ends at the other, but no circuit.
Why could nobody cross the Seven Bridges of Koenigsberg once each?
Euler drew the city as a network: land areas as vertices and bridges as edges. More than two of the land areas had an odd number of bridges, and an Eulerian trail allows at most two odd vertices, so no walk crosses every bridge exactly once.
Can a network have an odd number of odd vertices?
No. The degree sum is twice the number of edges, so it is even, and that forces the odd degrees to come in pairs.