6. BONUS Challenge Question (not required to be submitted but bonus marks will be awarded for correct solu- tions). The chromatic number of a graph G is the smallest number of colours needed to colour the vertices of G so that no two adjacent vertices get the same colour, (i.e., the minimum number k such that the vertices of G can be coloured with k colours so that no two adjacent vertices get the same colour). The length of a cycle in a graph is the number of edges (i.e. vertices) on that cycle. For any cycle C let its length be denoted by ICI. . (a) Let G be a graph. Suppose the following is true for G: for any two cycles C and C2 in G, if IC1l is odd and IC2l is odd then Ci and C2 have a vertex in common. Prove that such a graph G can be coloured with at most five colours . (b) In addition, find such a graph G whose chromatic number is equal to 5 . (Note, for example, that a graph that has at most one odd cycle satisfies the constraints described in (a))