1. (a) Prove that the inequality diam(G) n(G)-2 K(G) +1 (1) holds for any nontrivial connected graph G, where n(G), K(G) and diam(G) are the order, connectivity and diameter of G, respectively. (Recall that for any real number x, [x] denotes the largest integer no more than x.) [4 marks] (b) Show that the bound (1) above is sharp for graphs with connectivity 2 by constructing, for any integer n ≥ 3, a graph G such that n(G)= n, k(G) = 2 and diam(G) = | n 2 - +1. 2 [2 marks]

Fig: 1