A winning strategy that is a spanning tree

Two players and one graph with two marked vertices. Short secures a link, which fixes it permanently; Cut deletes one. Short wins by joining the two marks with secured links, Cut wins by separating them, and there is no third outcome — every link is eventually decided one way or the other.

Claude Shannon proposed it. David Gale reinvented a version of it, which was sold in 1960 as Bridg-It, a board game with plastic bridges. Alfred Lehman solved it in 1964, and the solution is of a kind the previous essay could not offer.

The criterion #

Short, moving second, wins exactly when the graph contains a subgraph holding both marked vertices that is the union of two edge-disjoint spanning trees of itself.

That sentence is a property of a graph. It mentions no play, no strategy and no opponent, and it can be checked by an algorithm that never looks at the game.

Two edge-disjoint spanning trees is a stronger condition than it first sounds, and reading it slowly is worth the trouble. A spanning tree of a vertex set touches every vertex in it; two of them being edge-disjoint means no link is in both; and the subgraph is allowed to be smaller than the whole graph, so the condition is about finding a suitable region rather than about the graph as a whole. What Short is looking for is a piece of the graph that contains both marks and has, in a precise sense, twice the connectivity it needs.

The strategy is worth stating because it is so short. Short holds two edge-disjoint routes. Cut deletes a link; that link belonged to one of the two trees; Short secures the corresponding link of the other. After each exchange Short still has two edge-disjoint routes, one of them partly secured, and the invariant survives to the end.

That is what a constructive solution looks like, and it is the exact opposite of the theorem that names no move.

Checked against the game #

Two computations, sharing no arithmetic. One plays every position out exhaustively, knowing nothing about trees. The other searches for the pair of trees, knowing nothing about the game. Agreement is evidence; agreement on one graph is an anecdote.

A thousand and twenty-four subgraphs, and the criterion and the solver give the same verdict on every one. That is the claim, and it is a claim about a sample rather than a proof, in the way everything on this site is: the proof is Lehman’s, and what is offered here is a check on the code.

The breakdown of those 1,024 is worth reading too. Seventy-one are a win for Short whoever starts. Four hundred and fifty-one are a win for Cut whoever starts. The remaining five hundred and two go to whoever moves first — which is the case that gives the game its name, and a game with only two of the three classes would be misnamed.

How the check was run #

The agreement above is a computation and it is worth saying what was computed, because “the criterion agrees with the game” is the kind of claim that can be true of the code and false of the mathematics.

The solver plays the game out. A position is the set of undecided links together with the partition of the vertices produced by everything Short has already secured — securing a link contracts it, deleting one removes it, and both are monotone, so the game is finite in the number of links and needs no depth limit. Short has won as soon as the two marks are in one contracted component; Cut has won as soon as no route between them survives even if Short took every remaining link.

The criterion never looks at any of that. It enumerates subsets of the surviving links, keeps the ones whose vertex set contains both marks and whose size is exactly twice the vertex count minus one, and then tries every way of splitting such a subset in half, testing both halves for being spanning trees. That is exponential and entirely adequate on ten links; Lehman’s own route is matroid union and runs in polynomial time.

The two share no code and no idea. What they share is the answer, on all 1,024 subgraphs.

That separation is the point of running both. A criterion checked against a re-implementation of itself proves nothing, and deciding whether one position beats another is itself a search unless somebody supplies a shortcut — so a shortcut that agrees with the search over a thousand cases is a shortcut worth having.

Where the criterion fails, and why #

The negative cases are more instructive than the positive ones, because they show what the criterion is really counting.

This is the figure that corrects the obvious guess. Redundancy is not the criterion; the criterion is a structural decomposition. Three routes of length two use six links on five vertices, and two spanning trees of five vertices would need eight — so the graph is two links short however many routes it appears to offer.

The grid is the interesting negative because it is large and still fails: six vertices and seven links, where the criterion wants ten. A reader who has absorbed “more links is better” has to watch a graph with more links than the doubled path lose to a graph with fewer. The next picture is the same failure with everything else stripped away, so that what is missing has nowhere to hide.

Three links on four vertices against the six the criterion asks for, and eight subgraphs of which Cut wins all eight. That is the floor. The graph that clears the criterion by the smallest possible margin is one link-count above it, and it is worth drawing next to the floor rather than next to the comfortable cases, because the two pictures differ by three links and by the whole verdict.

The counting half, and the rest of it #

The theta figure’s argument — six links on five vertices, and two spanning trees would need eight — is one instance of a condition worth stating in general, because it is the cheap half of the criterion and it settles most of the negative cases on this page by arithmetic alone.

A spanning tree of $v$ vertices has $v - 1$ edges, so two edge-disjoint ones need $2(v-1)$. A subgraph on $v$ vertices with fewer than $2(v-1)$ links cannot satisfy the criterion, whatever its shape.

Run it down the figures. The theta graph: six links, five vertices, needs eight — two short, and no arrangement helps. The bare grid and the single path fail it more comfortably still. And $K_4$: six links, four vertices, needs exactly six — which is why the caption says with nothing to spare, and why every one of its links is load-bearing.

So a reader can dismiss most graphs without looking for a partition at all. What the count cannot do is confirm: a subgraph with enough links may still fail, because the links can be in the wrong places.

Which is one case of the real condition #

The count is the coarsest member of a family, and the family is the theorem the criterion actually rests on.

Two edge-disjoint spanning trees exist exactly when, for every way of partitioning the vertices into $p$ groups, the number of links running between different groups is at least $2(p-1)$.

Take $p$ to be the number of vertices — every vertex its own group — and every link crosses, so the condition reads $|E| \geq 2(v-1)$: the count above. Take coarser partitions and the condition tightens in places the count cannot see, catching graphs with enough links overall and a bottleneck somewhere.

That is what “a structural decomposition rather than redundancy” means, said precisely. Redundancy is a global count. The criterion is a count that has to hold across every cut simultaneously, and a graph can be generous in total and mean in one place.

And why the game is easy #

That framing also explains the remark about matroid union, which the essay makes and leaves.

A condition quantified over every partition of the vertices looks unusable — there are exponentially many partitions, and the site’s own checker enumerates subsets and splits them, which it admits is exponential. The polynomial algorithm does not check the partitions. It searches directly for the two trees, using the fact that the forests of a graph are the independent sets of a matroid and that two matroids can be packed by an augmenting-path method.

So the criterion has three faces, and the essay uses two of them: a condition that is a statement about cuts, an algorithm that finds the object rather than checking the condition, and a strategy that reads off the object once found. The middle one is what makes the game polynomial and it is the one no picture shows.

That is the whole contrast with the essay next door. Hex is decided by four lines and its winning move is unknown; the switching game is decided by an object a person can be handed, checked in polynomial time, and played from directly. Both are games about connection, invented within a few years of each other. What separates them is that one of them turned out to have a matroid inside it.

Why it is a decomposition #

The criterion is a partition of a set of links into two pieces, each of which does the whole job on its own. That is a shape this site keeps meeting.

It is the same shape as the disjunctive sum turned inside out: instead of splitting a position into parts that do not interact, it splits a resource into two copies of a sufficient whole, so that losing one leaves the other intact. And it is the same shape as the mirroring strategy that solves two-heap Nim, where the resource split in two is the pair of heaps.

The general lesson: when a game is about a combinatorial structure rather than about positions on a board, there is a real chance the answer is a property of the structure. Lehman’s proof goes through matroid theory, where “two disjoint spanning trees” is an instance of matroid union, and the reason it is decidable in polynomial time is that matroid union is.

What a criterion buys that an existence proof does not #

Set the two solved games side by side and the difference is not about elegance.

Hex’s winning openings are known on three board sizes and are known because a search found them, one cell at a time; the strategy-stealing argument settles who wins on every board of every size and marks none of them. Lehman’s criterion does three things that argument cannot.

It decides an arbitrary position, not just the opening: hand it any subgraph and it answers. Stealing answers only about a fresh board.

It produces the move, because the trees are the strategy. Stealing produces nothing.

And it certifies the answer in a form somebody can check: the two trees are a short object, and verifying that they are edge-disjoint spanning trees is a matter of looking. That is precisely what a strategy is not a certificate says is normally unavailable — a proof that a player wins is usually a subtree of the game, exponentially large. Here the certificate is a pair of trees, and it is smaller than the graph.

The two players are not the same #

One detail that is easy to miss: Short and Cut do different things, so this is a partizan game — the two players have different move sets from the same position, exactly as in Domineering or Hackenbush.

That matters for what “solved” means here. Because the players differ, there are genuinely three questions rather than one — does Short win moving first, moving second, or neither — and the criterion answers the second directly. The other two follow: Short moving first wins whenever Short moving second does, plus the graphs where one secured link creates the two-tree condition.

The 1,024-subgraph survey is the place that shows all three classes populated, and it is worth noticing that the middle class is the largest. Most graphs are neither comfortable nor hopeless; they turn on who starts.

The surprise: the game in the box was the solvable one #

The chronology here is worth putting beside the previous essay’s.

Hex was invented in the 1940s, twice, and by mathematicians. Its answer — first player wins — arrived almost immediately and has produced no move in eighty years. The Shannon switching game was proposed by an engineer, sold as a commercial board game, and completely solved within a few years by a criterion anybody can apply.

The instinct is to say the second problem was easier. That is true and it is not the interesting part. What made it easier is that its winning condition is about a structure with a theory already attached. Connecting two vertices with a set of edges is a matroid question, matroids had been studied since the 1930s, and Lehman’s contribution was in large part recognising which existing theory the game was a question in.

Hex’s winning condition is also about connection, and it has no such theory, because Hex’s connections are constrained by a plane — the two players’ routes must cross, which is what makes the no-draw theorem true and also what makes the structure topological rather than matroidal. The topology gives the existence proof and nothing else.

So the two games are not far apart in difficulty by accident. The difference between them is which branch of mathematics their winning condition happens to sit in, and neither inventor chose that.

That reading is the one this whole field keeps arriving at. What “solved” means for a particular game is usually decided by whether its structure was already somebody else’s subject, and the games with clean answers are the ones that turned out to be asking a question the answer to which had been written down for other reasons.

What the picture cannot show #

The graphs here have four to six vertices, and Bridg-It is played on a board.

The translation from a Bridg-It board to a switching graph is real and is not drawn: one player’s dots become vertices, their possible bridges become links, and the other player’s bridges become deletions because two bridges cannot cross. That correspondence is the reason the game in the box is the game on the graph, and a picture of a small graph does not show it.

The second thing not shown is the matroid. Lehman’s proof is not the brute-force search this site runs; it is an argument about the structure of independent sets, and matroid union gives a polynomial-time algorithm where the search here enumerates subsets of subsets. The criterion drawn above is what the algorithm decides, and the algorithm is a different object from the picture.

Three outcomes, and what they are called here #

The survey found all three outcome classes populated, and it is worth translating them into the vocabulary the rest of this site uses, because the translation is not quite the obvious one.

A switching game is partizan, so its positions have values in principle, and the three classes above correspond to three of the four normal-play outcome classes: Short wins whoever starts is an L-position, Cut wins whoever starts is an R-position, and whoever moves first wins is an N-position. The fourth class — whoever moves loses — does not appear, and its absence is a fact about this game rather than an oversight.

The reason it is absent: the game has a goal rather than a last-move rule, so being obliged to move is never itself a disadvantage. Securing a link cannot hurt Short and deleting one cannot hurt Cut. That is the same monotonicity the previous essay’s stealing argument needed, and it is what rules out zugzwang here — which is why nothing in this field’s pawn endings, where zugzwang is the whole subject, looks anything like this.

So the two games in this pair of essays share a property that most games do not, and it is the property that makes both of them tractable in their different ways. Monotone games have no zugzwang, no P-positions of that kind, and a much simpler outcome structure than the games the sum is built for.

The convention, named #

This game does not end by somebody running out of moves. It ends when every link has been decided, and the winner is whoever achieved their goal.

That is a goal condition rather than the normal-play convention the rest of this site uses, and it is worth saying because the games in this field keep having them. Hex has a goal. Go is scored. Dots and Boxes is scored. The last-player-to-move rule is a convention that games invented for the theory adopt and games invented for players often do not — which is one of the reasons a field about applied cases needed to exist.

What survives is the determinacy: the game is finite, has no chance and no hidden information, and every position is a win for one side or the other. Everything above is a statement about which, and about how cheaply it can be found.

Where the ladder goes next #

switching opens with the constructive end of the spectrum this field is measuring.

The rung above it would be the matroid argument itself — why two edge-disjoint spanning trees is the right condition rather than a condition that happens to work, and what the same argument says about the games that are not switching games. That is a piece of structural mathematics rather than a set of solves, and it is the sort of rung this site should reach for once its graph machinery is doing more than drawing.