Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!brutus.cs.uiuc.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!simonson
From: simonson@uicbert.eecs.uic.edu
Newsgroups: comp.theory
Subject: Shannon's Switching Game
Message-ID: <88200006@uicbert.eecs.uic.edu>
Date: 29 May 90 01:47:00 GMT
Lines: 14
Nf-ID: #N:uicbert.eecs.uic.edu:88200006:000:742
Nf-From: uicbert.eecs.uic.edu!simonson    May 28 20:47:00 1990


In Shannon's Swithching 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?