Prove that if \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) , then \({\rm{gcd}}(a,bc) = 1\) .

(i)     A simple graph has e edges and v vertices, where \(v > 2\) . Prove that if all the vertices have degree at least k , then \(2e \ge kv\) .

(ii)     Hence prove that every planar graph has at least one vertex of degree less than 6.

EITHER

since \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) then

\(ax + by = 1\) and \(ap + cq = 1\) for \(x\), \(y\) , \(p\), \(q \in \mathbb{Z}\)     M1A1

hence

\((ax + by)(ap + cq) = 1\)     A1

\(a(xap + xcq + byp) + bc(yq) = 1\)     M1

since \((xap + xcq + byp)\) and \((yq)\) are integers     R1

then \({\rm{gcd}}(a,bc) = 1\)     AG

OR

if \({\rm{gcd}}(a,bc) \ne 1\) , some prime p divides a and bc     M1A1

\(p\) divides \(b\) or \(c\)     M1

either \({\rm{gcd}}(a,b)\) or \({\rm{gcd}}(a,c) \ne 1\)     A1

contradiction \( \Rightarrow {\rm{gcd}}(a,bc) = 1\)     R1

[5 marks]

(i)     each edge contributes 2 to the degree sum     R1

so \(2e = \) degree sum     R1

so \(2e \ge kv\)     AG

(ii)     \(k = 6\) so \(2e \ge 6v\)     M1

for a planar graph with \(v\) vertices and e edges, \(e \le 3v - 6\)     M1

so \(2e \le 6v - 12\)     A1

this is a contradiction so at least one vertex must have degree \( < 6\)     R1

Note: Alternative proofs are possible.

[6 marks]

A "verbal" argument rather than a symbolic approach was often taken, leading to some doubt about the validity of the "proofs". This discursive approach in trying to prove propositions often leads down blind alleys to confusion.

This was reasonably well done although clear proofs were not abundant and the same comments mentioned in (a) apply. In (ii) the word "Hence" was sometimes ignored. Candidates should realize that such "signpost" words are there to help them.