Graph Counting

First for some definitions : Let G = (V,E) be an undirected graph containing an edge e = (u,v) with u ≠ v. 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 x ∈ V, x′ = f(x) ∈ V′ is incident to an edge e′ ∈ E′ if and only if, the c