Richard Mansfield
We present a proof that the Shannon switching game on a graph with distinguished vertices A and B has a winning strategy for player Short iff the graph has a subgraph connecting A to B with two edge disjoint spanning trees. This theorem was first proved by Lehman in [11]. The difficulty is that his proof is phrased in terms of matroids and appears very difficult. However, I was able to cull a neat and short but elegant proof out of Lehman's work and that is what I want to present here. Using this proof, we will be able to give a strategy for player Cut for the graphs in which he has a win. This strategy is not be quite as neat as Short's strategy, and does not appear to be computationally feasible, but at least it does not involve any look ahead analysis.
We are given a multi-graph G with two distinguished vertices, A and B. The two players, Cut and Short play alternately. Short's move consists of marking an edge while Cut may remove any unmarked edge from the graph. If Short can succeed at marking an entire path from A to B, he wins. Otherwise Cut wins. As we shall see shortly, if G contains two trees connecting A to B having no edges in common but sharing the same vertex set, then Short has a winning strategy even if he goes second. Our main theorem is the converse, that if he has a winning strategy from the second position, then there must be two such trees. Brualdi has written an excellent expository article about the switching game. See [1]. This article has been essentially repeated as a section in his book [2, Section 11.6,].
Let us say that a graph is positive if it has an edge disjoint pair of spanning trees. Then what we wish to show is that G has a positive subgraph containing both A and B if and only if Short has a winning strategy even if he plays second. The reader may easily verify that the union of two positive graphs is either disconnected or positive.
The reader may also also easily verify that if there is a positive subgraph connecting A to B, then Short has a winning strategy. He proceeds as follows: If Cut removes an edge from one of the two trees, Short finds an edge in the other tree which reconnects the broken tree and marks it. He then has two spanning trees for the subgraph with only marked edges in common.
Let us prove the converse. Suppose Short goes second and has a
winning strategy. We must prove the existence of a positive
subgraph. So Cut goes first and deletes an edge.
Short then marks an
edge, call it a. By induction, we may assume that there
are two trees, 
and 
from A to
B having a common vertex set but only the edge a in common.
We now need a lemma. We shall state and use the lemma and
only when the main proof is finished will we come back and
prove it. The lemma is the following: If S and T are two
trees with a common vertex set and at most one edge in common and if
P and Q are two distinct vertices of these trees, then either
has a positive subgraph connecting P to Q or it has
two spanning trees with
only one edge in common having the additional property
that in at least one of the trees the common edge lies on the
path from P to Q.
As a first use of this lemma, we may as well assume that a
lies on the path in from A to B.
If every edge lying on the path from A to B in
was spanned by a positive subgraph of G, then the union of these
positive subgraphs
would be a positive graph connecting A to B. So choose an edge b
not spanned by any positive subgraph of G and
lying on the path in
from A to B.
Consider the fact that Cut could have chosen
b on his first move instead of the one he did choose.
Again, by induction, we get trees 
and 
avoiding b
with a common vertex set and at most one edge in common joining
A to B.
Deleting the edge a from splits into two
connected components with A in one of the components and
B in the other. Deleting the edge b from
has a similar effect. Thus, since and are both
connected graphs containing both A and B, the graphs
and 
are both connected. In order to apply the
Lemma, we also need the condition that the graphs have only
one edge in common. For these graphs this need not be the
case since may overlap and may overlap
. However, since spans every edge in , we may
further take all the edges of 
away from
and still have a connected graph. Similarly,
we may delete 
from without losing connectivity. Thus, the two graphs,
and 
are both connected. Both these graphs span
the edge b, but neither contain b. Furthermore, they have at
most one edge in common. Using the lemma again,
we see that 
must have two spanning trees whose
only common edge lies on the path in one of the two trees
between the two ends of b.
That tree may then be disconnected
by deleting the common edge from it and then reconnected by
adding the edge b. This proves the theorem and we are left with
proving the lemma.
To this end, let S and T be the two given trees. A
spanning chain is a sequence 
such that
is the path in S from P to Q and for each i <
n/2, the path 
is the path in T spanning an edge in
and 
is the path in S spanning an edge in
. If the common edge is not on any path in any
spanning chain, then let S' to be all the edges e in S
for which there is a spanning chain with a path containing e,
and let T' be all
the edges e in T for which there is a spanning chain with a
path containing e. We
can easily see that S' and T' are two edge
disjoint trees with a common vertex set connecting the two
given vertices and thus the
first possibility holds.
We complete the lemma by induction on the length of the
shortest chain containing the common edge.
Let 
be such a shortest chain.
If n is 0, there is nothing to prove. If n is
even, then 
is a path in S, otherwise it is a path in
T. In any event, the common edge lies in . Proceed as
follows: Delete the common edge from the appropriate tree.
(S if n is even, T if n is odd.) Then reconnect the tree
by adding to it the edge in 
spanned by . This
new doubled edge lies on a shorter spanning chain and so the
lemma follows by induction.
The above proof yields a strategy for player Cut. Suppose it is Cut's turn and Short does not have a forced win. Cut should then find a pair of trees S and T connecting A to B with a common vertex set but only one unmarked edge in common. If there are no such trees, he may play at random. Finding such a pair however, he should perform the construction given in the lemma to ensure that the common edge lies on the path in S from A to B. He should then find an edge on the path in T from A to B which is not in any positive subgraph of G and remove it. Our proof has just shown that if this procedure allows Short to get a forced win, then Short already had a forced win before Cut made his move.
to3em