Number of spanning trees
Task number: 3925
Determine the number of spanning trees of the following graphs:
Variant
\(C_m \oplus_e C_n\) (merge along an edge)
Solution
We divide the spanning trees into two groups: those containing the edge \( e \) and the others.
In the first group it is then necessary to build the spanning tree of \( C_m \) from the remaining \( m-1 \) edges of the cycle, which can be done in \( m-1 \) ways. The same argument holds for \( C_n \).
The spanning trees in the second group correspond to the spanning trees of \( (C_m \oplus_e C_n) -e = C_ {m + n-2} \).
Answer
The graph \(C_m \oplus_e C_n\) has \((m-1)(n-1) + m+n-2\) spanning trees.
Variant
\(C_m \oplus_e K_n\)
Hint
Use the fact that there are \( 2n ^ {n-3} \) spaning trees of \( K_n \) with an prescribed edge \( e \).
Solution
Each spanning tree of \( K_n \) can be extended in \( m-1 \) in ways on a spanning tree of the whole graph.
It remains to determine the number of spanning trees \( T \), whose intersection with \( K_n \) is disconnected, i.e. it has two components. (These spanning trees necessarily contain \( m-1 \) edges from \( C_m \), all except \( e \).)
If we add the edge \( e \) to \( T \cap K_n \), we get a spanning tree of \( K_n \) again. So they are as many as the spanning trees of \( K_n \) containing a fixed edge \( e \).
Answer
The graph \(C_m \oplus_e K_n\) has \(n^{n-2}(m-1)+2n^{n-3}\) spanning trees.
Variant
\(K_m \oplus_e K_n\)
Answer
The graph \(K_m \oplus_e K_n\) has \(2m^{m-3}n^{n-3}(m+n-2)\) spanning trees.
Variant
\(K_n \div e\) (subdivide one edge)
Answer
The graph \(K_n \div e\) has \((2n-2)n^{n-3}\) spanning trees.
Variant
\(K_n \div E\) (subdivide all edges)
Answer
The graph \(K_n \div E\) has \(n^{n-2}2^{{n \choose 2}-(n-1)}\) spanning trees.
Variant
\(2K_n\) (duplicate all edges in parallel)
Answer
The graf \(2K_n\) has \(n^{n-2}2^{(n-1)}\) spanning trees.
Variant
\(K_{m,n}\)
Hint
Adjust the proof using the incremental building methd or calculate the number of spanning trees by determinants.
Solution
Let \( A \) be the class of the bipartition of \( K_{m, n} \) with \( m \) vertices and \( B \) the remaining.
We count in two ways the number of spanning trees rooted in a vertex of \( A \), where the arrows leading from \( A \) to \( B \) are numbered by \( 1,…, m-1 \) (no arrow leaves the root). Arrows leading from \( B \) to \( A \) have no numbers.
There are \( \kappa (K_{m, n}) m (m-1)! \) such modified spanning trees.
For the second method of calculation, proceed as follows: First, select one arrow from each vertex \( B \) to any vertex \( A \). This get a total of \( m^n \) options. We now have \( m \) components, each looking like a star centered in \( A \).
Incrementally add the \( m-1 \) arrows from \( A \) to \( B \). In the \( i \)-th step, we add an arrow numbered \( i \) leading to any vertex \( B \) but from the root of some other component of \( A \). For the \( i \)-th step it means \( n (m-i) \) options.
By adjusting equality \( \displaystyle \kappa (K_{m, n}) m (m-1)! = m ^ n \prod_{i = 1} ^{m-1} n (m-1) \) we get the result.
For another combinatorial proof see http://dx.doi.org/10.1016/0012-365X(90)90377-T
Answer
The graph \(K_{m,n}\) has \(m^{n-1}n^{m-1}\) spanning trees.
Variant
\(K_{m,n} - e\)
Answer
The graph \(K_{m,n} - e\) has \((m-1)(n-1)m^{n-2}n^{m-2}\) spanning trees.
Variant
\(K_{m,n} \div E\)
Answer
The graph \(K_{m,n} \div E\) has \(2^{(m-1)(n-1)}m^{n-1}n^{m-1}\) spanning trees.
