I'm trying to figure out the number of spanning trees that are in the graph depicted below,
I am currently working on the idea of splitting up the graphs into subgraphs, because then I'm able to apply certain formulas to calculate the number of spanning trees.
My problem is, though, how do I add them together in the end?
For the beforementioned graph, I've divided them into 1 complete bipartite graph, 1 complete graph and 2 simple graphs.
The complete graph can be calculated using Cayley's formula,
$\tau(k_n) = n^{n-2}$ giving me $\tau(k_4) = 4^{4-2} = 16$ spanning trees
The complete bipartite graph can be calculated using Scoin's formula, $\tau(k_{n,m}) = n^{m-1} m^{n-1}$ giving me $\tau(k_{3,3}) = 3^{3-1} 3^{3-1} = 81$ spanning trees
The two simple graphs each have 8 spanning trees (found from lookup)
I've found nowhere though how this can be added together (and even if it can).
So my question is: how, if at all possible, do you sum up the number of spanning trees from several subgraphs?
First time on math.stackexchange, so any feedback is appreaciated.
On each subgraph, a spanning tree must visit each vertex, so a choice of a spanning tree on each is equivalent to a choice of a spanning tree on the whole graph.
How many choices are there? Just multiply. The general formula (assuming the subgraphs meet their neighbors in a single vertex without introducing any new cycles) looks like: $$ \tau(G_1 \cup \cdots \cup G_k) = \tau(G_1) \cdots \tau(G_k). $$
Can you finish from there?