Graphs & networks
Points joined by lines: edges, degrees, trees, and routes.
Pen and paper is fine · no calculator needed why?
Opens at level 47. You're level 1. You can read and practice here now.
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
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.
practice
Every pair joined
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
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
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
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.