0
$\begingroup$

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)$?

$\endgroup$

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

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

1
$\begingroup$

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?

Yes. (Although the correct terms are disconnected and connected).

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

No. There are two cases to consider: exactly one of the extra edges is present in the spanning tree, or both are present. Your expression corresponds to one of those cases.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – J. Lastin May 14 at 13:38
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Peter Taylor May 14 at 14:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.