Skip to content
Get started

Spanning trees of a wheel

A network has a hub connected to each of 55 outer nodes, and the 55 outer nodes form a ring (each joined to its two neighbours). That is 1010 links on 66 nodes.

How many spanning trees does this network have (sets of 55 links that connect all 66 nodes without a cycle)?

Show hints (3)+
  1. Matrix-tree theorem: delete one row and column of the Laplacian and take the determinant.
  2. Delete the hub; what remains is 3I3I minus a cycle's adjacency matrix - a circulant.
  3. Eigenvalues of the nn-cycle adjacency are 2cos⁡(2πk/n)2\cos(2\pi k/n).

Answer

Reveal answer →

121

Create a free account to see the full worked solution and track your progress.

Interview format: Trading Aptitude Tests, Prop Trading

Related questions