Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph.

For example, for $K_n$ this is $n!$, for a path on $n$ vertices this is $2^{n-1}$. These are clearly the largest and smallest possible values. Other values:

• For a star with $n-1$ leaves, the answer is $2(n-1)!$
• For a cycle graph, the answer is $n2^{n-2}$

The answers seem to be very divisible; for instance, for the 4-vertex graphs we get 8, 12, 14, 16, 20, 24. (The answer is automatically even.)

This must have been studied, but we can't find the key word. It seems possibly related to the Tutte polynomial.

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. (Let us call this the sweepout number until we find a reference elsewhere.)

For example, for $K_n$ this is $n!$, for a path on $n$ vertices this is $2^{n-1}$. These are clearly the largest and smallest possible values. Other values:

• For a star with $n-1$ leaves, the answer is $2(n-1)!$
• For a cycle graph, the answer is $n2^{n-2}$

The answers are sometimes divisible; for instance, for the 4-vertex graphs we get 8, 12, 14, 16, 20, 24. (The answer is automatically even.)

This must have been studied, but we can't find the key word. It seems possibly related to the Tutte polynomial.

Can this be computed in any reasonable way?

Update: Divisibility does not continue for large graphs. For an example that also hints at the motivation, consider the dual graph to the division of Pennsylvania into congressional districts. (This is a graph with 18 vertices). The sweepout number for this graph is 10,672,157,119,848, which is not round.