Suppose T is a fixed labeled tree on $n$ vertices. How many labeled graphs on $n$ vertices have T as a subgraph?
I know a tree is a graph in which all vertices have an edge and there are no circuits. And I know that a subgraph is a graph whose vertices and edges are subsets of another graph. But I'm not really sure how to think about this problem?
The question amounts to asking in how many different ways you can add $0$ or more edges to $T$ without adding any vertices. HINT: A tree on $n$ vertices has $n-1$ edges. The complete graph on $n$ vertices has $\binom{n}2$ edges; you can add any collection of those edges that aren’t already in $T$.