Coaching Centre
The language of networks
Vertices, edges and degree, the sum of degrees rule, connected networks, and the difference between a walk, a trail, a path and a cycle.
Look at the Sydney Trains map on the wall of any carriage. Stations are dots, lines join the stations you can travel between, and the drawing is nowhere near to scale. Nobody cares that Blacktown is drawn too close to Parramatta. All that matters is what connects to what. That idea is the whole of network maths.
Vertices, edges and degree
- A network is a set of points called vertices (one is a vertex) joined by lines called edges.
- Vertices are the things: stations, suburbs, people, computers. Edges are the links between them: tracks, roads, friendships, cables.
- The degree of a vertex is the number of edges that meet at it. A vertex with degree $0$ is isolated.
- A network is connected if you can get from every vertex to every other vertex along edges.
Here is the one rule worth remembering. Every edge has two ends, and each end adds $1$ to the degree of the vertex it touches. So when you add up all the degrees, every edge has been counted exactly twice.
Two quick consequences. The sum of degrees is always even. And the number of vertices with an odd degree is always even, because odd numbers can only add to an even total in pairs.
For the network above, find the degree of each vertex and check the sum of degrees rule.
Walks, trails, paths and cycles
A route through a network is a list of vertices, each joined to the next by an edge. Exams use four names for routes, and the difference is all about what is allowed to repeat.
| Name | Edges repeat? | Vertices repeat? | Think of it as |
|---|---|---|---|
| Walk | allowed | allowed | any route at all |
| Trail | no | allowed | never use the same road twice |
| Path | no | no | never visit the same place twice |
| Cycle | no | only start = end | a path that comes back home |
The names are nested. Every path is a trail, and every trail is a walk, but not the other way round. A closed trail that passes through some vertex twice on the way is called a circuit.
Using the network in Example 1, name each route: (a) F–A–B–C–D (b) A–B–E–A (c) A–B–D–E–B–C (d) A–B–E–B–C
Networks in real life
The same vocabulary works wherever things are linked:
- Transport: stations and lines, suburbs and roads, airports and flights.
- Utilities: houses and water pipes, NBN nodes and fibre, substations and power lines.
- Social networks: people and friendships. Your degree is your number of friends, and the sum of degrees rule says the total number of "friend counts" across a class is even.
- Projects: tasks and the order they must happen in (you'll meet these in Year 12).
In Edit roads, add and remove roads and watch the sum of degrees. Can you ever make the number of odd vertices equal to $1$ or $3$? Why not?
Disconnect Granville from everything else. What happens to "Connected?"
Switch to Trace a route. Make a path of $4$ edges, then a cycle, then a trail that isn't a path, then a walk that isn't a trail.
Your turn
A network has $8$ vertices. Four have degree $3$, three have degree $2$ and one has degree $4$. How many edges does it have?
Show the working
Sum of degrees $= 4 \times 3 + 3 \times 2 + 1 \times 4 = 12 + 6 + 4 = 22$. Number of edges $= 22 \div 2 = 11$.
The degrees of the vertices of a network add to $20$. How many edges does it have?
Each edge is counted twice in the sum of degrees, so edges $= 20 \div 2 = 10$.
Which route uses no edge twice but visits a vertex twice?
A trail bans repeated edges but allows repeated vertices. If a vertex repeats, it is a trail but not a path.
In the network from Example 1, how many vertices have degree $4$?
B (edges to A, C, D, E) and E (edges to A, B, D, F) both have degree $4$. That's $2$ vertices.
Could a network have vertices of degree $3, 3, 2, 1$?
$3 + 3 + 2 + 1 = 9$ is odd, but a sum of degrees must be even ($2 \times$ edges). Equivalently, there are three odd vertices, and odd vertices come in pairs.
A network is connected when:
Connected only needs a route between each pair, not a direct edge. A direct edge between every pair is a much stronger condition.
In a group chat network, each vertex is a student and each edge means "has messaged". Eight students have each messaged exactly $3$ others. How many edges?
Sum of degrees $= 8 \times 3 = 24$, so edges $= 24 \div 2 = 12$.
Every path is also:
A path repeats no vertices, so it can't repeat an edge either. That makes it a trail, and every trail is a walk.
A connected network has $7$ edges and $6$ vertices. Five vertices have degrees $1, 2, 2, 3, 4$. Find the degree of the sixth vertex.
Sum of degrees $= 2 \times 7 = 14$. The five known degrees add to $12$, so the sixth is $14 - 12 = 2$.
Exam style: In the Example 1 network, which route is a cycle?
B–C–D–B uses edges BC, CD and DB, returns to B and repeats no other vertex. A–B–C–D–E doesn't return home, E–B–D–E–A–E repeats E in the middle (and EA–AE uses an edge twice), and the last one repeats edge AF.
Exam style: A network has $6$ vertices. Each vertex is joined to exactly $3$ others. How many edges does it have?
Sum of degrees $= 6 \times 3 = 18$. Edges $= 18 \div 2 = 9$.