I had asked:
Jim Hendrickson of the chemistry department here just asked me whether there was a good algorithm for finding the set of all one- or two-edge cut sets of a graph. When pressed, he said he'd actually like to find the cut which leaves two pieces as close to the same size as possible. And Dylan algorithm'd: OK, after 30 seconds of thought, here's the algorithm for finding all edges that can be removed to disconnect the graph. Start by finding a spanning tree for the graph, and mark all components as belonging to different 2-connected components. Then, for each edge not in the spanning tree, find the path within the spanning tree between its two endpoints, and merge the 2-connected components of the vertices along that path. The edges that join different 2-connected components are the edges you're looking for. (These edges are necessarily in every spanning tree.)
Ah, quite right. Along similar lines, I came up with the following for the two-edge cut sets. Build a spanning tree and a matrix which lets you easily walk between any pair of vertices along the tree, just as you say. Each edge in the tree is assigned a list, initially empty, of its "cut partners". Then for each edge e not in the tree, walk along the tree between e's two endpoints and add e to the list of "cut parnters" of each edge you use. At the end, any edge in the tree whose cut-partner list is of length 0 is a cut edge, and any whose list is of length 1 is half of a two-edge cut set, with the list's sole element being the other edge you need to cut. It may not be deep, but it's quick... --Michael Kleber kleber@brandeis.edu