Prove that a graph containing a triangle cannot be bipartite.

Prove that the number of edges in a bipartite graph with n vertices is less than or equal to \(\frac{{{n^2}}}{4}\).

At least two of the three vertices in the triangle must lie on one of the two disjoint sets     M1R1

These two are joined by an edge so the graph cannot be bipartite     R1

[3 marks]

If there are x vertices in one of the two disjoint sets then there are (n – x) vertices in the other disjoint set     M1

The greatest number of edges occurs when all vertices in one set are joined to all vertices in the other to give x(n – x) edges     A1

Function f(x) = x(n – x) has a parabolic graph.     M1

This graph has a unique maximum at \(\left( {\frac{n}{2},\frac{{{n^2}}}{4}} \right)\).     A1

so \(x(n - x) \leqslant \frac{{{n^2}}}{4}\)     R1

[5 marks]

Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.

Part (a) was usually done correctly but then clear argument for parts (b) and (c) were rare.