Is there an algorithm for determining whether a given undirected graph has two edge-disjoint spanning trees...

combinatorics/shannon.switching.game New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Is there an algorithm for determining whether a given undirected graph
has two edge-disjoint spanning trees (which guarantees a win for the
connecting player in Shannon's Switching Game)?

In Shannon's Switching game, two players alternately choose edges of a
given undirected graph until all the edges are chosen.  There are two
distinguished vertices in the graph, u and v.  The goal of one player
is to connect these two vertices and the goal of the other player is to
separate them.  It is known that the "connecting" player can always win
if there are two edge disjoint spanning trees of the graph.

Does anyone know an algorithm for determining whether a given
undirected graph has two edge disjoint spanning trees?  If this result
is well known, is it a special case of a larger theory?  and if such an
algorithm exists, and one determines that a given graph has two edge
disjoint spanning trees, then is it easy to find them?

-- simonson@uicbert.eecs.uic.edu

Show solution

The answer to all of the questions is YES.

This is a result in matroid theory.

Some references are:

1.  Alfred Lehman, "An Introduction to Matroid Theory", SIAM
    J. 12 (1964), pp 687-725.

2.  John Bruno and Louis Weinberg, "A Constructive Graph-Theoretic
    Solution of the Shannon Switching Game", J. IEEE Trans. Circuit
    Th. CT-17 (1970), pp 74-80.

3.  W. J. Tutte, "Lectures on Matroids", J. of Research of the National
    Bureau of Standards 69B (1973), pp 1-77.

Lehman was the original "solver" of this game.  Unfortunately, none of
the above references is comprehensible.  The standard texts on Matroid
Theory generally don't give the solution but refer the reader to one of
these three texts.

-- David G. Cantor <dgc@math.ucla.edu>