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.

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]

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.