Spanning trees of a wheel
A network has a hub connected to each of outer nodes, and the outer nodes form a ring (each joined to its two neighbours). That is links on nodes.
How many spanning trees does this network have (sets of links that connect all nodes without a cycle)?
Show hints (3)+
- Matrix-tree theorem: delete one row and column of the Laplacian and take the determinant.
- Delete the hub; what remains is minus a cycle's adjacency matrix - a circulant.
- Eigenvalues of the -cycle adjacency are .
Answer
Reveal answer →Final answer
121
Create a free account to see the full worked solution and track your progress.
Interview format: Trading Aptitude Tests, Prop Trading