A graph has n vertices with degrees 1, 2, 3, …, n. Prove that \(n \equiv 0(\bmod 4)\) or \(n \equiv 3(\bmod 4)\).

Let G be a simple graph with n vertices, \(n \geqslant 2\). Prove, by contradiction, that at least two of the vertices of G must have the same degree.

as each edge contributes 1 to each of the vertices that it is incident with, each edge will contribute 2 to the sum of the degrees of all the vertices     (R1)

so \(2e = \sum {{\text{degrees}}} \)     (A1)

\(2e = \frac{{n(n + 1)}}{2}\)     A1

\(4|n(n + 1)\)     A1

n and n + 1 are coprime     R1

Note: Accept equivalent reasoning e.g. only one of n and n + 1 can be even.

\(4|n{\text{ or }}4|n + 1\)     A1

\(n \equiv 0(\bmod 4){\text{ or }}n \equiv 3(\bmod 4)\)     AG

[6 marks]

since G is simple, the highest degree that a vertex can have is n – 1     R1

the degrees of the vertices must belong to the set \(S = \{ 0,{\text{ }}1,{\text{ }}2,{\text{ }} \ldots ,{\text{ }}n - 1\} \)     A1

proof by contradiction

if no two vertices have the same degree, all n vertices must have different degrees     R1

as there are only n different degrees in set S, the degrees must be precisely the n numbers 0, 1, 2, ..., n – 1     R1

let the vertex with degree 0 be A, then A is not adjacent to any of the other vertices     R1

let the vertex with degree n – 1 be B, then B is adjacent to all of the other vertices including A     R1R1

this is our desired contradiction, so there must be two vertices of the same degree     R1

[8 marks]

Only the top candidates were able to produce logically, well thought-out proofs.

Only the top candidates were able to produce logically, well thought-out proofs.