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.
more of the idea
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.
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.
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.
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
New here? Start the four-problem warm-up. No sign-up.
Every pair joined
worked example
How many edges does the complete graph K₅ have (every pair of its 5 points joined)?
- Each pair gives one edge: C(5, 2) = 5 × 4 ÷ 2 = 10.
Answer: 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?
- 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.
Answer: 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?
- Each tree has one edge fewer than it has vertices, so 6 trees have 6 fewer edges than vertices.
- 79 − 6 = 73.
Answer: 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
- 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.
Answer: neither