Solve (b)

2. (10 marks) Two trees are edge-disjoint if there is no edge appearing in both of them (a) (3 marks) Let G be a graph with 2 edge-disjoint spanning trees. What is the least number of vertices, n', that G can have? Give an example of a graph on n' vertices which has 2 edge- disioint spanning trees. (b) (4 marks) For general n 2 n', describe a graph on n vertices and a weight function such that the graph has exactly two edge-disjoint minimum spanning trees. Explain why your construction is correct. (c) (4 marks) Prove that if a graph has fewer than 2k vertices, then it cannot have k spanning trees such that every pair of them is edge-disjoint, when k 2 3