Date | November 2014 | Marks available | 4 | Reference code | 14N.3dm.hl.TZ0.2 |
Level | HL only | Paper | Paper 3 Discrete mathematics | Time zone | TZ0 |
Command term | Prove that and Use | Question number | 2 | Adapted from | N/A |
Question
Use the pigeon-hole principle to prove that for any simple graph that has two or more vertices and in which every vertex is connected to at least one other vertex, there must be at least two vertices with the same degree.
Seventeen people attend a meeting.
Each person shakes hands with at least one other person and no-one shakes hands with
the same person more than once. Use the result from part (a) to show that there must be at least two people who shake hands with the same number of people.
Explain why each person cannot have shaken hands with exactly nine other people.
Markscheme
let there be \(v\) vertices in the graph; because the graph is simple the degree of each vertex is \( \le v - 1\) A1
the degree of each vertex is \( \ge 1\) A1
there are therefore \(v - 1\) possible values for the degree of each vertex A1
given there are \(v\) vertices by the pigeon-hole principle there must be at least two with the same degree R1
[4 marks]
consider a graph in which the people at the meeting are represented by the vertices and two vertices are connected if the two people shake hands M1
the graph is simple as no-one shakes hands with the same person more than once (nor can someone shake hands with themselves) A1
every vertex is connected to at least one other vertex as everyone shakes at least one hand A1
the degree of each vertex is the number of handshakes so by the proof above there must be at least two who shake the same number of hands R1
Note: Accept answers starting afresh rather than quoting part (a).
[4 marks]
(the handshaking lemma tells us that) the sum of the degrees of the vertices must be an even number A1
the degree of each vertex would be \(9\) and \(9 \times 17\) is an odd number (giving a contradiction) A1
[2 marks]
Total [10 marks]
Examiners report
Generally there were too many “waffly” words and not enough precise statements leading to conclusions.
Misconceptions were: thinking that a few examples constituted a proof, thinking that the graph had to be connected, taking the edges as the pigeons not the degrees. The pigeon-hole principle was known but not always applied well.
Generally there were too many “waffly” words and not enough precise statements leading to conclusions.
Similar problems as in (a).
Generally there were too many “waffly” words and not enough precise statements leading to conclusions.
Many spurious reasons were given but good candidates went straight to the hand-shaking lemma.