5. Suppose you are given a set S of n distinct points in the plane. Let A and B represents a partition of S, i.e. ACS, BCS,S- AUB, and AnB-. Define the distance between A and B, denoted by d(A, B), as the minimum among Euclidean distances between pair of points, where one point is from A and the other from B, i.e dA, B)ninab Our task here is to find a partition of S into two non-empty sets A and B that max- imizes d(A, B). For this, we define a complete graph G (V, E) on n vertices and (2) edges on these points as follows. Each vertex in V represents a distinct point of S, and there is an edge between every pair of (distinct) vertices, where the weight of an edge e = (u,u) is Euclidean distance between the points corresponding to u and v. Consider a minimum spanning tree T of G. Let e be the most expensive edge in T (i.e. e is the last edge added to T by Kruskal's algorithm). Let Vi and V2 be the two sets of vertices in the connected components obtained after the removal of e from T. Show that the points corresponding to Vi and V2 forms the required partitioning of S. (Recall that Euclidean distance between two points a (3,5) and b (4.2) is ab(3-4)2 (5- 2)2-V10.)