1. (10 points total) Let us say that a connected undirected graph G = (V, E) has a "surplus" of A if |E| = |V] + A. Remarks: A tree has a surplus of -1. A near-tree as defined on Question 1 of Problem Set 2 has a surplus of 0. End of remarks. For any undirected graph G = (V, E), and any subset E' of E, we define E' to be special if each connected component of the subgraph (V, E') has a surplus of 1, 0, or 1. Remarks: For the matroid studied in Question 1 of Problem Set 2, we defined an inde- pendent set of an undirected graph G = (V, E) as a subset E' of E such that each connected component of (V, E') is either a tree or a near-tree, i.e., each connected component of (V. E') has a surplus of -1 or 0. End of remarks. In each of the following parts, let k be an integer greater than 1 and let G = (V. E) be a complete undirected graph with 4k vertices. Thus |E] = (15). (a) (4 points) Prove that there is a maximal special subset E' of E such that E'] = tk+1. (A special subset of E is maximal if it is not properly contained in any other special subset of E.) (b) (4 points) Prove that there is a maximal special subset E" of E such that E"| = 5k. (C) (2 points) Let S denote the set of all special subsets of E. Prove that (E, S) is not a matroid. Hint: Use the results of parts (a) and (b)