Question Type 5: Finding all the possible Tree subgraphs Exercises

Find the number of spanning trees of the path graph $P_n$ in terms of $n$.

How many spanning trees does the complete graph $K_5$ have?

Determine the number of spanning trees in the complete bipartite graph $K_{2,3}$.

How many spanning trees does the complete bipartite graph $K_{3,4}$ have?

Find the number of spanning trees of the cycle graph $C_n$ in terms of $n$.

In the star graph $S_n$ (one central vertex connected to $n$ leaves), how many subtrees with $k$ edges are there?

How many subtrees on 3 vertices does the complete graph $K_5$ contain?

Verify Cayley’s formula by computing the number of spanning trees of $K_6$.

Given the graph $G$ on vertices $\{1,2,3,4\}$ with edges $\{1\!\!\!\text{-}2,2\text{-}3,3\text{-}4,4\text{-}1,1\text{-}3\}$, enumerate all spanning trees and determine their number.

For the graph formed by two triangles sharing one vertex (vertices $\{1,2,3,4,5\}$ and edges $\{1\text{-}2,2\text{-}3,3\text{-}1,3\text{-}4,4\text{-}5,5\text{-}3\}$), find the number of spanning trees using deletion–contraction.

Use deletion–contraction on the graph consisting of a triangle $1$–$2$–$3$–$1$ with a pendant edge $3$–$4$ to find its number of spanning trees.

Use Kirchhoff’s Matrix–Tree Theorem to find the number of spanning trees of the graph $G$ on vertices $\{1,2,3,4\}$ with edges $\{1\!\!\!\text{-}2,2\text{-}3,3\text{-}4,4\text{-}1,1\text{-}3\}$.