Let G be a graph which may also contain loops and multiple e

Let G be a graph, which may also contain loops and multiple edges. Let e be an edge that is not a loop. Define G e as G with the edge e deleted, and G : e as the graphs arising from G by deleting the edge e and subsequent gluing of the end-vertices of e into a single vertex. The other edges are preserved, and so this operation can produce new loops or multiple edges. Let T(H) denote the number of spanning trees of graph H.

(a) Prove that T(G) = T(G e) + T(G : e).

(b) Derive the number of spanning trees of the 3-dimensional cube by a calculation based on (a)

Solution

Let G=(V,E) be a graph (or directed graph) containing an edge e=(u,v) with uv. Let f be a function which maps every vertex in V\\{u,v} to itself, and otherwise, maps it to a new vertex w. The contraction of e results in a new graph G=(V,E), where V=(V\\{u,v}){w}, E=E\\{e}, and for every xV, x=f(x)V is incident to an edge eE if and only if, the corresponding edge, eE is incident to x in G.

Vertex identification (sometimes called vertex contraction) removes the restriction that the contraction must occur over vertices sharing an incident edge. (Thus, edge contraction is a special case of vertex identification.) The operation may occur on any pair (or subset) of vertices in the graph. Edges between two contracting vertices are sometimes removed. If v and v\' are vertices of distinct components of G, then we can create a new graph G\' by identifying v and v\' in G as a new vertex v in G

First note that G is given to be a finite group. We define mapping : G G such that (x) = x 1T(x). Clearly mapping so defined is welldefined. Also (a) = (b) a 1T(a) = b 1T(b) T(a)(T(b))1 = ab1 T(ab1 ) = ab1 But T(x) = x implies x = e, so (a) = (b) implies ab1 = e, i.e. a = b. Thus mapping is one-to-one. But since G is finite, therefore being one-to-one implies is onto too. But onto implies that if some g G, then it has its pre-image in G, i.e. g = x 1T(x) for some x G. Hence every element g of G can be represented as x 1T(x) for some x G.