# Number of spanning trees on graph disjoint union. [duplicate]

This question is an exact duplicate of:

Consider a graph G on 200 vertices, created by adding the following edges $$(v_1, v_{101}), (v_2, v_{102})$$ to the disjoint union of two complete graphs $$K_{100}$$ with respective vertices $$v_1,...v_{100}$$ and $$v_{101},...,v_{200}$$. What is the number of spanning trees for graph G?

I know that $$t(K_n) = n^{n-2}$$ according to Cayley's formula.

But I'm not sure about the disjoint union, does that mean that after performing a disjoint union, I get a discontinuous graph with 2 components, where each component is a complete graph $$K_{100}$$, that is then made continuous by the edge addition?

And if that is the case, would the answer then be $$t(G) = 2\cdot(t(K_{100})^2)$$?

## marked as duplicate by Mike Earnest, Shailesh, Cesareo, Adrian Keister, Xander HendersonMay 15 at 13:46

This question was marked as an exact duplicate of an existing question.

But I'm not sure about the disjoint union, does that mean that after performing a disjoint union, I get a discontinuous graph with 2 components, where each component is a complete graph $$K_{100}$$, that is then made continuous by the edge addition?
And if that is the case, would the answer then be $$t(G) = 2\cdot(t(K_{100})^2)$$?
• Okay, I know that number of trees containing a specific edge $e\in E$ on a complete graph is $t_e(K_n) = 2n^{n-3}$, could I then just count the second graph as an edge $(v_1,v_2)$ and do the same for the first graph "being" the edge $(v_{101},v_{102})$ to get $t(G) = 2\cdot(t(K_{100})^2) + t_e(K_{100})^2$? – J. Lastin May 14 at 13:38
• Not quite, although that's a nice idea for how to reduce it to a solved problem. In the case where both $(v_1, v_{101})$ and $(v_2, v_{102})$ are present, the path $v_1 \to^* v_2$ either uses both of the cross-edges or neither. If it uses both then $v_1$ and $v_2$ are not connected in the lower-indexed $K_{100}$, so the higher indexed one is effectively serving as an edge $v_1 - v_2$. Otherwise it's the other way round. So I think we should get $t(G) = 2 t(K_{100})^2 + 2 t(K_{100}) t_e(K_{100})$. – Peter Taylor May 14 at 14:43