Graph 2 Prove the following statements using one example for each (consider n > 5). (a) A graph G is bipartite if and only if it has no odd cycles. (b) The number of edges in a bipartite graph with n vertices is at most (n2 /2).

(c) Given any two vertices u and v of a graph G, every uv walk contains a uv path.

(d) A simple graph with n vertices and k components can have at most (n-k).(n-k+1)/2 edges.