Lesson 3

Optional Problems.

Problems on the matrix-tree theorem.

1. (20 points) Find \(\tau(K_{n,m})\), the number of spanning trees of the complete bipartite graph \(K_{n,m}\).
2. (20 points) Fix any two orientations of \(G\) and form incidence matrices \(I\) and \(I'\). Prove that the reduced determinants \(\det(I_{i}I_{i}^{\top})\) and \(\det(I'_{i}I_{i}'^{\top})\) are equal, where \(I_{i}\) (resp. \(I'_{i}\)) denotes the matrix obtained by deleting row \(i\).
3. (20 points) Let \(G\) be a connected graph with Laplacian \(L\). Prove that \(\det(L_{i;i})=\det(L_{j;j})\) for all \(i,j\), where \(L_{i;i}\) denotes the principal minor obtained by deleting row \(i\) and column \(i\) (not via matrix-tree theorem).