Show that a graph is bipartite if and only if it contains only cycles of even length.

Suppose the graph is bipartite so that the vertices belong to one of two disjoint sets M, N.     M1

Then consider any vertex V in M. To generate a cycle returning to V, we must go to a vertex in N, then to a vertex in M, then to a vertex in N, then to a vertex in M, etc.     R1

To return to V, therefore, which belongs to M, an even number of steps will be required.     R1

Now suppose the graph contains only cycles of even length.     M1

Starting at any vertex V, define the set M as containing those vertices accessible from V in an even number of steps and the set N as containing those vertices accessible from V in an odd number of steps.     R1

Suppose that the vertex X belongs to both M and N. Then consider the closed walk from V to X one way and back to V the other way. This closed walk will be of odd length. This closed walk can be contracted to a cycle which will also be of odd length, giving a contradiction to the initial assumption.     R1

There can therefore be no vertices common to M and N which shows that the vertices can be divided into two disjoint sets and the graph is bipartite.     R1

Consider any edge joining P to vertex Q. Then either \({\text{P}} \in {\text{M}}\) in which case \({\text{Q}} \in {\text{M}}\) or vice versa. In either case an edge always joins a vertex in M to a vertex in N so the graph is bipartite.     R1

[8 marks]

Many candidates made a reasonable attempt at showing that bipartite implies cycles of even length but few candidates even attempted the converse.