Intuition behind the formula for number of graphs with $n-3$ bridges

Question

The number of labelled graphs with $n$ vertices and $n-1$ bridges is $n^{n-2}$ which follows from Cayley's formula, and there are no graphs with $n-2$ bridges, it strikes me that the formula for the number of labelled graphs with $n-3$ bridges it seems to be (tested for few value of $n$ up to $8$) $${n-1\choose 2}\cdot n^{n-3}$$ And for $n-4$ bridges it seems to be (tested for few value of $n$ up to $8$) $$10\cdot{n-1\choose 3}\cdot n^{n-4}$$ This pattern doesn't seem to continue (or at least I haven't noticed it) except that $n^{n-k}$ divides the number of labelled graphs with $n-k$ bridges. I'm wondering if there is some intuition to those formulas and for the divisibility by $n^{n-k}$ or some generalization to bigger number of bridges.

Answer 1

If a graph has $n-3$ bridges then if we remove all those bridges, what's left will have $n-2$ components, so will be either two disjoint edges or a triangle. But the two disjoint edges option isn't actually possible (since those edges would also have been bridges), therefore the graph has exactly one triangle and $n-3$ bridges.

Mimic Prüfer's proof of Cayley's formula as follows. First choose three vertices to form a triangle, and make a note of these ($\binom n3$ choices). Now remove the lowest-numbered leaf at each step and write down its neighbour; keep going until only the triangle remains. We will write down a sequence of $n-3$ vertices, and the only restriction is that the last one has to be one of the three triangle vertices, so that is $3n^{n-4}$ possible sequences. You can check that, given a set of triangle vertices and a sequence of vertices as above, there is exactly one way to reconstruct the graph. Thus there are $\binom n3\times3n^{n-4}=\binom{n-1}2\times n^{n-3}$ such graphs.

For $n-4$ bridges, the argument is similar. After removing all bridges there must be one (bridgeless) component of $4$ vertices, and $n-4$ isolated vertices. However, even if you know which vertices ($a,b,c,d$, say) are in the group of $4$, there are multiple possibilities. You could have a cycle, which could be $abcd$, $abdc$ or $acbd$. You could have a cycle with one diagonal (any of the above with either of two diagonals, giving $6$ possibilities). Or you could have all six edges between the four. So there are $10$ possibilities, which is where the factor of $10$ comes from.

With $n-5$ bridges, however, it becomes more complicated. When you remove the bridges, having one $5$-vertex component is no longer the only possibility - you could also have two triangles.