## 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.