Consider a tree T in which the degree of each vertex is either 1 or 3. Let n = |V(T)|, where V() is the set of vertices.
What is the number of distinct simple graphs G such that T is a spanning tree of G?
So far here's what I've done:
I've shown that n is even. I've shown that T has $\frac n 2 + 1$ leaves.
T is a spanning tree of G => V(T) = V(G)
I'm using a theorem that for any finite set V, there are $2^{ |V|\choose2}$ distinct simple graphs with vertex set V.
Hence there are $2^{n\choose2}$ distinct simlpe graphs.
Then I've used another theorem that for $n\ge2$ there are $n^{n-2}$ distinct trees with n vertices.
Therefore, we have $n^{n-2}$ spanning trees with n vertices.
Hence, total distinct simple graphs = $n^{n-2} . 2^{n\choose2}$
check?