Intuition behind the formula for number of graphs with $n-3$ bridges 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.
 A: 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.
