关于每条边添加额外顶点的完全图生成树数量的疑问
Great observation! Let's break down why that extra factor of $2^{\binom{n-1}{2}}$ makes sense, step by step:
First, let's clarify the graph we're working with: we take the complete graph $K_n$, and insert a new vertex into every single edge. So each original edge $uv$ in $K_n$ becomes two edges: $uw$ and $wv$, where $w$ is the new vertex we added. Let's call this expanded graph $G$.
A spanning tree of $G$ has to include all vertices in $G$: the original $n$ vertices from $K_n$, plus the $\binom{n}{2}$ new vertices we added. That's a total of $\frac{n(n+1)}{2}$ vertices, so the spanning tree needs $\frac{n(n+1)}{2} - 1 = \frac{(n+2)(n-1)}{2}$ edges.
Now, let's tie this back to Cayley's formula, which tells us $K_n$ has $n^{n-2}$ spanning trees. For each spanning tree $T$ of $K_n$, we can build spanning trees of $G$ in the following way:
First, take the $n-1$ edges in $T$. Each of these edges was split into two edges in $G$. To include the corresponding new vertices in our spanning tree, we have to keep both edges for each original tree edge—if we only kept one, the new vertex would be disconnected from the rest of the tree. This gives us $2(n-1)$ edges, forming a subtree that includes all original vertices and the $n-1$ new vertices tied to $T$'s edges.
Next, we have $\binom{n}{2} - (n-1) = \binom{n-1}{2}$ remaining new vertices. Each of these corresponds to an edge in $K_n$ that's not part of $T$ (let's call these "non-tree edges"). For each such vertex $w$ (connected to original vertices $u$ and $v$), $u$ and $v$ are already connected via the subtree we built from $T$. If we added both $uw$ and $wv$, we'd create a cycle (since $u$ and $v$ are already connected), which isn't allowed in a spanning tree. Instead, we can choose either $uw$ or $wv$ to add—this connects $w$ to the tree without creating a cycle.
Each of these $\binom{n-1}{2}$ non-tree edge vertices gives us 2 independent choices. Multiply all those choices together, and we get $2^{\binom{n-1}{2}}$ ways to expand each spanning tree of $K_n$ into a spanning tree of $G$.
Multiply that by the number of spanning trees of $K_n$ (from Cayley's formula), and we end up with exactly the formula you noticed:
$$n^{n - 2} \times 2^{\binom{n - 1}{2}}$$
备注：内容来源于stack exchange，提问作者meerkat
