Question Type 5: Finding all the possible Tree subgraphs Exercises

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

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

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.

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

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

Calculate the number of spanning trees for the complete bipartite graph $K_{3,4}$.

A graph $G$ is formed by two triangles sharing a single vertex. The vertex set is $V = \{1, 2, 3, 4, 5\}$ and the edge set is $E = \{1-2, 2-3, 3-1, 3-4, 4-5, 5-3\}$.

Find the number of spanning trees of $G$ using the method of deletion–contraction.

Find the number of spanning trees of the cycle graph $C_n$ in terms of $n$. [3 marks]

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-2, 2-3, 3-4, 4-1, 1-3\}$.

Find the number of spanning trees of the path graph $P_n$ in terms of $n$. [2 marks]

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

In the star graph $S_n$ (consisting of one central vertex connected to $n$ leaves), determine the number of subtrees with $k$ edges, where $1 \le k \le n$.