Warm-up
Three quick ones from earlier work. Try each in your head or on paper before you open the answer.
- From Year 7: work out 5 + 4 + 3 + 2 + 1.
Answer
15. - From Year 8: solve 2e = 38.
Answer
e = 19. Divide both sides by 2. - From Year 10: how many different pairs can be chosen from 4 people?
Answer
6. Each of 4 people pairs with 3 others, giving 12, but each pair has been counted twice.
Words used in this lesson
- graph
- a set of vertices joined by edges. For example: a map of bus stops.
- vertex
- a point where edges can meet. For example: a village.
- edge
- a line that joins two vertices. For example: a bridge.
- degree
- the number of edges at a vertex. For example: a vertex on 4 edges has degree 4.
- handshake result
- the rule linking the sum of the degrees to the number of edges. For example: each edge has two ends.
Can seven guests each shake hands with exactly three others?
At a family gathering in Nairobi there are seven guests. Every guest greets exactly three of the others with a handshake, and nobody shakes hands with the same person twice. Draw seven dots for the guests and a line for each handshake: that drawing is a graph. Each dot is a vertex, each line is an edge, and the degree of a vertex is the number of edges that end there.
Predict first: is it possible to arrange the handshakes so that all seven guests have degree 3? Then add edges in the figure, watch the degrees and their sum, and decide whether your prediction was right.
5 edges: the degrees are 1, 2, 2, 2, 2, 1, which add to 10, and 2 times 5 is 10.
Show me the steps
- 3 edges, AB, BC and CD: the degrees are 1, 2, 2, 1, 0, 0, they add to 6, and 2 times 3 is 6. Two vertices have odd degree.
- 6 edges, the whole hexagon: every vertex has degree 2, the sum is 12, and no vertex has odd degree.
- 9 edges, the hexagon and its three long diagonals: every vertex has degree 3, the sum is 18, and all six vertices have odd degree.
- Any number of edges: each new edge adds 1 to two degrees, so the sum goes up by 2 every time and always equals 2 times the number of edges.
Every edge has two ends, so it adds 1 to two degrees. Adding the degrees of all the vertices counts each edge twice: the sum of the degrees is 2 × the number of edges. This is called the handshake result.
The sum is always even, so a list of degrees with an odd sum cannot belong to a graph (and each degree must be small enough for the number of vertices). These tests rule lists out; passing them does not prove a graph exists.
Two common slips. Counting a crossing in the drawing as a vertex: two lines that cross without a dot are not joined, and only the dots are vertices. And forgetting that a graph is not a map: moving a vertex or bending an edge does not change the graph, because only the pairs that are joined matter.
Worked examples
1. A graph has edges AB, AC, BC and CD. Find the degree of each vertex and check the handshake result.
- A is on AB and AC, so 2. B is on AB and BC, so 2. C is on AC, BC and CD, so 3. D is on CD only, so 1.
- The degrees add to 2 + 2 + 3 + 1 = 8, and there are 4 edges, so 8 = 2 × 4.
2. A graph has four vertices with degrees 2, 2, 3 and x. What can x be?
- The sum is 7 + x, and it must be even, so x is odd.
- With four vertices a degree is at most 3, so x is 1 or 3.
3. How many edges has a graph in which each of 5 vertices is joined to every other?
- Each vertex has degree 4, so the sum of the degrees is 5 × 4 = 20.
- Half of that is 10 edges.
Your go. The first step is given. A graph has 8 vertices and every vertex has degree 5. How many edges does it have, and could it exist?
- The sum of the degrees is 8 × 5 = 40.
- Use the handshake result to find the number of edges, then decide whether that number is a whole number.
Check the answer
The number of edges is 40 ÷ 2 = 20. The sum is even, so the handshake result does not rule the graph out, and one does exist: place the 8 vertices round an octagon and join each vertex to every other vertex except its two neighbours, which gives degree 7 − 2 = 5.
Check before you go on
1. Which list of degrees can belong to a graph with four vertices?
Your turn
Start at Level 1 and go as far as you can. Type negative numbers with a minus sign, for example -7. A wrong answer gets a reason, not just a cross: read it, then try again.
Level 1 · Getting started
2. A district in Kerala has 9 villages joined by 14 footbridges, each bridge joining two villages. What is the sum of the degrees of the 9 villages?
3. A graph has six vertices with degrees 3, 2, 4, 1, 2 and 2. How many edges does it have?
Level 2 · Building
4. At a school sports day in Lagos, 12 students each exchange a flag with exactly 3 others. Each exchange is between two students. How many exchanges are there?
5. A graph has five vertices with degrees 4, 3, 3, 2 and x. What is the smallest value x can have?
Level 3 · Stretch
6. A network of 10 relay stations in the hills near Pokhara has 17 links. Every station has degree 3 or degree 4. How many stations have degree 3?
7. In a chess tournament in Almaty, every player plays every other player exactly once, and 45 games are played. How many players are there?
Something to think about
A graph may have two edges between the same pair of vertices, or an edge that starts and ends at the same vertex (a loop, which counts 2 towards its vertex's degree). Does the sum of the degrees still equal twice the number of edges?
One way to think about it
Yes. Every edge still has two ends, and each end adds 1 to some vertex's degree, so each edge adds 2 to the sum, including a loop, which adds 2 to a single vertex. The result needs only that every edge has two ends.
Exit ticket
8. A graph has 7 vertices and 6 edges. Six of the vertices have degree 1. What is the degree of the seventh vertex?