← All solutions

This problem can be solved by finding the 2-vertex-connected components of the graph (or in other words, by the decomposition of the graph based on its articulation vertices). The set of 2-vertex-connected components form a tree, and it is easy to prove that it is necessary and sufficient to place an escape shaft in each leaf of this tree. The total number of ways in which this can be done is just the product of the sizes of the 2-vertex-connected components corresponding to those leafs.

There is a tricky border case to take care of, which is the case when the entire graph is 2-vertex-connected is a special case; then 2 escape shafts are needed (1 escape shaft is never sufficient since the junction of that single escape can collapse) and they can be placed in (V2) ways, where V is the number of vertices.