skip to content

How many distinct spanning-tree overlays can a fully-meshed cluster of n labelled nodes have?

level: seniorimportance: nice to knowfreq 22%

answer

  1. labelled, not shapes
  2. a complete graph's tree count
  3. n to the power n minus two
  4. four nodes give sixteen
  5. Laplacian cofactor for partial meshes

basics

~20 s

n to the power n-2, by Cayley's formula: 16 for four nodes, 125 for five, 1296 for six. When only some pairs can be linked, the matrix-tree theorem counts instead, as a cofactor of the graph's Laplacian determinant.

solid answer

~50 s

For a complete graph on `n` labelled nodes the answer is **Cayley's formula**, `n^(n-2)`: three nodes give 3, four give 16, five give 125, six give 1296. The count is over **labelled** trees — two overlays that look alike but attach different nodes are different overlays, which is the sense that matters when the nodes are distinct machines. For a partial mesh, where only certain pairs may be linked, the tool is the **matrix-tree theorem**: build the Laplacian `D - A` (degrees on the diagonal, minus one for each link), delete any one row and its matching column, and the determinant of what remains is the number of spanning trees. It agrees with Cayley on the complete graph, and it gives, for example, exactly `n` spanning trees for a ring of `n` nodes — drop any one of its `n` links.

go deeper

for a junior

Know that a fully meshed set of nodes can be wired as a tree in many different ways, and that the number grows far faster than the node count does.

for a middle

State Cayley's formula and compute it for small n, and be explicit that it counts labelled trees, not shapes. Check yourself against the four-node case: 16, not 2.

for a senior

Use the count as a feasibility argument: the space is superexponential, so enumeration is off the table and the matrix-tree theorem is what answers the partial-mesh version.

for a principal

Treat the count as a measure of topological freedom. Many valid overlays mean rebuilding after a failure has choices; a count near one means the structure is already forced.

## What is being counted A **spanning tree** of a graph is a subset of its links that keeps every node and forms a tree: connected, acyclic, exactly `n-1` links. The counting question is how many such subsets a given graph has. This is a structural count with no notion of cost attached — every spanning tree is as good as another here, and picking a cheapest one under link weights is a different subject entirely. Two counts must not be confused: - **Labelled** trees treat the nodes as distinguishable. Two overlays are different if any node has a different set of neighbours. - **Unlabelled** trees count shapes only, with node identities erased. The gap is dramatic and grows fast. Nodes are real machines with identities, so the labelled count is almost always the one a question means. | n | labelled trees, `n^(n-2)` | distinct shapes | |---|---|---| | 2 | 1 | 1 | | 3 | 3 | 1 | | 4 | 16 | 2 | | 5 | 125 | 3 | | 6 | 1296 | 6 | For `n = 4` the two shapes are the chain and the star; the 16 labelled trees are 4 stars (one per possible centre) and 12 chains (the `4!/2 = 12` distinct orderings of four nodes in a line). ## Cayley's formula **Cayley's formula** states that the number of labelled trees on `n` nodes is `n^(n-2)`, which is also the number of spanning trees of the complete graph on `n` nodes, since in a complete graph every tree on those nodes is available. The standard way to see it is a bijection: encode each labelled tree as a sequence of `n-2` node labels, and show that every such sequence decodes to exactly one tree. Counting sequences of length `n-2` over `n` labels gives `n^(n-2)` directly. In an interview, the bijection is the idea to describe — the encoding's step-by-step mechanics are not the point. ## Partial meshes: the matrix-tree theorem Real clusters are not fully meshed: some pairs cannot link at all. Then Cayley does not apply, and the **matrix-tree theorem** does. The recipe is mechanical: 1. Build the **Laplacian** matrix `L = D - A`, where `D` is diagonal with each node's degree and `A` has a 1 for each linkable pair. 2. Delete any one row and the column with the same index — it does not matter which, the result is the same. 3. Take the determinant of the remaining `(n-1) x (n-1)` matrix. That number is the count of spanning trees. Two checks worth carrying: on the complete graph it reproduces `n^(n-2)`, and on a ring of `n` nodes it returns `n`, matching the obvious argument that a ring becomes a tree exactly when you drop one of its `n` links and there are `n` ways to do that. ## Why the number, not just the formula, matters - **The count explodes.** `n^(n-2)` grows faster than any exponential in `n`: at 10 nodes it is 100 million, at 20 it is past `10^23`. No procedure that enumerates candidate overlays and picks one can work beyond a handful of nodes, no matter how fast each step is. - **It bounds what a search can promise.** Any selection method must exploit structure rather than survey the space. That is a statement about the size of the space, which is exactly what this count provides. - **It quantifies how much freedom a topology has.** A graph whose spanning-tree count is 1 has exactly one way to be wired as a tree — it already is one. A count of `n` means the graph is a ring. A large count means many equally valid overlays exist, which is what lets a system rebuild a different one after a failure. - **Zero is the degenerate answer.** A disconnected graph has no spanning tree at all, and the theorem duly returns 0, so the count doubles as a connectivity test. ## Where candidates slip The frequent error is answering with the shape count — "two, a chain and a star" for four nodes — because the labelled/unlabelled distinction was skipped. The second is reaching for the number of ways to *delete* links: a complete graph on 4 nodes has 6 links and choosing 3 of them gives 20 subsets, but 4 of those 20 are a triangle plus an isolated node, leaving the 16 that are trees. The formula is not a binomial coefficient.

  • Why does choosing n-1 of the mesh's links not give the same number?
    Because some of those subsets are not trees. On four nodes the complete graph has 6 links and 20 ways to choose 3 of them, but 4 choices form a triangle plus an isolated node, which is cyclic and disconnected. Removing those leaves 16, matching Cayley's formula. A count of subsets ignores structure; the formula counts only the structured ones.
  • What does a spanning-tree count of zero tell you about a graph?
    That it is disconnected. A spanning tree must reach every node, and no subset of links can connect what has no link crossing between two parts. The matrix-tree determinant returns 0 in exactly that case, so the count is also a connectivity test.
  • How many spanning trees does a ring of n nodes have?
    Exactly `n`. A ring has `n` nodes and `n` links, so it is one link above the tree floor and holds a single cycle; dropping any one of its `n` links leaves a connected graph with `n-1` links, which is a tree. No other subset works, since dropping two links disconnects it.

saying these in an interview costs you the question

  • Answers with the count of tree shapes, ignoring node labels
  • Computes a binomial coefficient over the mesh's links
  • Applies Cayley's formula to a partially connected graph
  • Thinks the count is manageable enough to enumerate
  • Confuses counting spanning trees with choosing a cheapest one