Let n be a positive integer. Let Kn,2 be the simple graph with vertex set {1,2,…,n}∪{−1,−2} such that two vertices of Kn,2 are adjacent if and only if they have opposite signs (i.e., each positive vertex is adjacent to each negative vertex, but no two vertices of the same sign are adjacent). We regard Kn,2 as a multigraph in the usual way.
(a) Without using the matrix-tree theorem, prove that the number of spanning trees of Kn,2 is n⋅2n−1.
(b) Let Kn,2′ be the graph obtained by adding a new edge {−1,−2} to Kn,2. How many spanning trees does Kn,2′ have?