A (k, l)-dumbbell graph is obtained by taking a complete graph on k (labeled) nodes and a complete graph on l (labeled) nodes, and connecting them by a single edge. Find the number of spanning trees of a dumbbell graph.
Do I have use Kruskal's algorithm for this problem? I am not sure where to begin.
On
Hint 1: The number of spanning trees in a complete graph $K_n$ of order $n$ is $n^{n -2}$ according to Cayley's formula.
Hint 2:
Knowing the number of trees spanning each of the two maximal cliques (maximal complete subgraphs) of the dumbbell graph, use the fundamental counting principle to find the number of trees spanning the full dumbbell graph.
Hint 3:
Let $n$-dumbbell denote the dumbbell graph created by joining by means of a bridge edge two complete graphs $K_n$. Then, for $n \in [3, 4, 5, 6, \ldots]$ the number of spanning trees is 9, 256, 15625, 1679616, $\ldots$, respectively.
Full solution:
Any trees spanning the full graph will have to use the bridge edge. Thus, each of the $n^{n -2}$ trees spanning one of the maximal cliques can be connected to each of the $n^{n -2}$ trees spanning the other maximal clique by using the bridge edge. Using the fundamental counting principle, we have that the total number of spanning trees of a dumbbell graph of order $n$ is $n^{n -2} \cdot n^{n -2} = (n^{n -2})^2$.
Hints