Graphs & networks
Points joined by lines: edges, degrees, trees, and routes.
Pen and paper is fine · no calculator needed why?
Opens at level 47.
the lesson
Read the lesson
The idea
A graph is a set of points (vertices) joined by lines (edges). A vertex's degree is the number of edges touching it.
Every edge has two ends, so adding up all the degrees counts each edge twice. That one fact gives the edges from a degree list, and the edges of a complete graph, where every pair of n points is joined.
A tree is connected with no cycles (closed loops), and has one edge fewer than vertices. An Euler path traces every edge exactly once; an Euler circuit also ends where it started. The odd-degree vertices decide which you get.
Techniques
Add the degrees, then halve
- Add up all the degrees.
- Halve the total: each edge was counted at both ends.
- Every pair of n points joined: each has degree n − 1, so n × (n − 1) ÷ 2 edges.
worked example
At a meeting, 8 people each shake hands once with every other person. How many handshakes are there?
- Each person shakes 7 hands: 8 × 7 = 56.
- Each handshake was counted twice: 56 ÷ 2 = 28.
Answer: 28
Trees: one edge fewer
- A tree with n vertices has n − 1 edges.
- A forest of c trees with n vertices in all has n − c edges.
worked example
A forest (a graph with no cycles) is made of 4 separate trees with 30 vertices in all. How many edges does it have?
- Each tree has one edge fewer than it has vertices.
- 30 − 4 = 26.
Answer: 26
Count the odd degrees
- Count the vertices with odd degree.
- None: an Euler circuit.
- Exactly two: an Euler path from one odd vertex to the other, but no circuit.
- Four or more: neither.
worked example
A connected graph has vertex degrees 2, 3, 4, 3 and 2. How many of its vertices have odd degree?
- The two vertices of degree 3 are odd.
- Exactly two, so an Euler path but no circuit.
Answer: 2
Tips by skill
- TipEvery pair joined: Every pair gives one edge: n × (n − 1) ÷ 2.
- TipDegrees to edges: Add all the degrees, then halve: each edge is counted once at each end.
- TipTrees: One tree: vertices minus 1. A forest: vertices minus the number of trees.
- TipTrace every edge once: In a connected graph, count the odd degrees. None: a circuit. Exactly two: a path but no circuit. Four or more: neither.
Watch out for
- Forgetting to halve. Adding the degrees, or multiplying n by n − 1, counts every edge from both ends.
- Giving a tree one edge per vertex. That many edges would close a cycle.
- Calling two odd vertices a circuit. A circuit needs every degree to be even.
skills · practice stats
-
Every pair joined not tried yet
worked example
How many edges does the complete graph K₅ have (every pair of its 5 points joined)?
Answer: 10
- Each pair gives one edge: C(5, 2) = 5 × 4 ÷ 2 = 10.
-
Degrees to edges not tried yet
worked example
A graph’s vertices have degrees 1, 3, 2, 4, 2 and 2. How many edges does it have?
Answer: 7
- Each edge adds 1 to the degree of both of its ends, so the degrees add up to twice the number of edges.
- 1 + 3 + 2 + 4 + 2 + 2 = 14, and 14 ÷ 2 = 7.
-
Trees not tried yet
worked example
A forest (a graph with no cycles) is made of 6 separate trees with 79 vertices in all. How many edges does it have?
Answer: 73
- Each tree has one edge fewer than it has vertices, so 6 trees have 6 fewer edges than vertices.
- 79 − 6 = 73.
-
Trace every edge once not tried yet
worked example
A connected graph has vertex degrees 2, 2, 5, 3, 3, 3, 4 and 4. Which does it have?
- an Euler path but no circuit
- an Euler circuit
- cannot tell
- neither
Answer: neither
- Four vertices have odd degree (their degrees are 5, 3, 3 and 3). A trail can start or end at only two of them.
- So there is no Euler path and no Euler circuit: neither.
rest ladder
- 1 day
- 3 days
- 7 days
- 14 days
- 30 days
- 60 days
- mastered · every 90 days