IB Mathematics Applications & Interpretation 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$.