Cut is Short on another graph

Two essays have now been written about the Shannon switching game and both of them are about Short. A winning strategy that is a spanning tree gives Lehman’s criterion for Short moving second — a pair of edge-disjoint spanning trees — and the first move is a link that is not there shows that the same test, asked of the graph with a link from A to B added, settles Short moving first. Cut’s side of the game appears in both only as the thing whose replies are enumerated.

That asymmetry is in the rules. Short builds and Cut destroys, Short’s goal is a route and Cut’s is the absence of one, and a criterion phrased in trees is a criterion about routes. It is fair to ask whether Cut has anything of its own to look for — some object a Cut player could find on the board, as Short finds trees, that settles the game from the other end.

On any graph that can be drawn without two links crossing, Cut does, and the object is not a new idea. It is a pair of trees on a different graph, and the game Cut plays is exactly the game Short plays there.

A board with both players on it #

The box Gale sold in 1960 makes the point before any graph is drawn.

Bridg-It has two players and two colours of dot. Blue joins the top of the board to the bottom by building bridges between neighbouring blue dots; red joins left to right between neighbouring red dots. Bridges may not cross. Nobody deletes anything.

And yet it is a switching game, because of the crossings. Every blue bridge crosses exactly one red bridge, so building a blue bridge forbids one red bridge for ever, and building a red bridge forbids one blue one. Seen from blue’s side, blue secures links and red deletes them. Seen from red’s side, the roles swap. One board, two switching games, and each player’s securing is the other’s deleting.

The figure counts what each side can usefully build. Blue’s top row is one point and its bottom row another, since a bridge along an end row joins a row to itself; what is left is thirteen bridges on eight points. Red’s board is blue’s turned a quarter, and it has thirteen bridges on eight points too.

The dual, drawn #

What Bridg-It does with two colours of dot, any graph drawn in the plane does with its own faces.

Draw a switching graph with A and B on the outside, and imagine the link from A to B running round the outside as well — the imaginary link of the essay before this one, doing a second job. The drawing now divides the plane into regions. Put a point inside every region. Where two regions meet along a link, join their points with a new link crossing that one. The region outside the imaginary link and the region inside it, on the outer edge of the drawing, become the two marked points of the new graph; call them A′ and B′.

That new graph is the planar dual, and the correspondence is exact in the way Bridg-It’s crossings are. Deleting a link of the graph removes the wall between two regions, which is securing the dual link across it — the two regions are now one. Securing a link of the graph makes that wall permanent, which is deleting the dual link — the two regions can no longer be joined across it.

The bridge makes a good first example because nothing changes. Its two inner faces are the triangles either side of the rung; the outer face splits into the part above and the part below. Joining them up gives four points and five links arranged as — the bridge. The bridge is its own dual. That is why the earlier essay found it a win for whoever moves first: the game looks the same from both chairs.

Why the two games are one #

The correspondence between moves is not yet an argument that the outcomes correspond, and the missing step is the one fact about the plane the whole construction rests on.

A route from A to B in the graph and a route from A′ to B′ in the dual cannot both exist among undeleted links. The route from A to B, closed up by the imaginary link round the outside, is a loop in the plane with A′ on one side and B′ on the other, and any route from A′ to B′ has to cross it — through one of its links, which would have to be both secured and deleted. And when every link is decided, one of the two routes does exist: the links Short failed to secure are deleted, their duals are secured, and if they do not join A′ to B′ then the secured links of the graph wall A off from B′'s side all the way round, which is a route from A to B.

So at the end of every game exactly one of the two graphs has its route. Short wins on the graph precisely when Short on the dual — who is Cut, relabelled — loses. Cut moving second on a graph wins exactly when Short moving second wins on its dual, and the same holds moving first.

The single path shows the correspondence at its bluntest. Every link of a path has the outer face on both sides — above and below — so its dual is a link between A′ and B′, and the path’s three links become three links in parallel. Cut wins the path by deleting any link; Short wins three parallel links by securing any one of them, since Cut can delete only one at a time. The figure prints those as one verdict because they are one verdict.

Every subgraph, twice #

An identity that follows from a picture of the plane should be checked against play, and the check is easy to state: take each subgraph of a graph, solve it as Cut, build the matching position on the dual, solve that as Short, compare.

The matching position has one subtlety. A subgraph is a graph with some links already deleted, and in the dual those links are already secured — so the dual position starts with their ends merged, not with the links missing. Getting that backwards produces a position that is a different game, and the comparison would fail at once.

8,584 subgraphs across eight drawings, and the two games agree on every one. The largest is the Bridg-It board of size three, with thirteen links and 8,192 subgraphs, each played out as blue on blue’s graph and as red on red’s.

The drawings are also checked as drawings. The faces are traced by walking round each point’s links in the order of their angles, and a drawing with two crossing links, or two links drawn on top of each other, gives walks that are not faces. Euler’s relation catches that — points minus links plus faces must be two for a connected drawing — and a drawing that fails it is refused rather than given a dual. It is the same relation that turns Sprouts from a game of drawing curves into a count, and it does the same job here: it is the one fact about the plane that can be checked by arithmetic rather than by looking.

It also explains why the dual has the size it has. Every link of the graph is crossed by exactly one dual link, so the two have the same number of links; and the dual’s points are the faces, so Euler’s relation fixes how many there are. A drawing with p points and l links has l − p + 2 faces, and splitting the outer face with the imaginary link adds one more. The bridge has five links on four points, three faces, and four dual points once the outer face is split — four points and five links again, which is the arithmetic behind its being its own dual. That is why the path with every link doubled, which has two links drawn along each segment, is not in the table: the pairs of parallel links need separating in the drawing before the faces between them exist.

The link that leads nowhere #

The bridge with a spur, from the essay before this one, has a link that Short should never secure first: the spur, hanging off A into a point with no other link. Securing it is a wasted move. Its dual says why in a way the earlier argument did not.

A link with the same region on both sides is a link that no loop in the drawing passes through, and its dual is a loop — a link from a point back to itself. A loop is worth nothing to either player. Securing it merges a point with itself; deleting it separates nothing.

So the spur is a pass twice over. For Short, securing it joins nothing to anything that matters. For Cut, deleting it is securing a loop on the dual, which is equally nothing. The earlier essay found the spur the one losing opening of six; the dual shows that it would be a losing move for Cut as well, and that its uselessness is a fact about the drawing — a link with one face — rather than about whose turn it is.

Bridg-It, counted #

Bridg-It’s board is its own dual at every size, turned a quarter. That settles half of the question — the game looks the same from both chairs — and a count settles the rest.

On a board of size n, blue has n + 1 rows of n dots, and with the end rows merged that is n(n − 1) + 2 points. Two spanning trees on those points need twice that less one, which is 2n² − 2n + 2 links. The board has n² upright bridges and (n − 1)² crosswise ones, which is 2n² − 2n + 1.

One link short, at every size. So no board passes Lehman’s test as it stands, and blue moving second never has the two trees. With the link from A to B added, the count is exact, and the test is passed exactly when those links split into two trees with nothing left over. They do, on every board in the table. The split is found by exchange — each link is offered to one of two forests, and when neither will take it a chain of swaps makes room — which is the polynomial method Lehman’s theorem points to; no subset is enumerated, which is how a board of size eight, with 113 links, fits in the table at all.

So by the equivalence of the earlier essay, blue moving first wins every Bridg-It board, and blue moving second loses every one, and the two boards small enough to play out confirm it by play.

Two proofs that the first player wins, and what each supplies #

That conclusion is an old one, and there is a second route to it that uses none of the trees.

The board is symmetric under the quarter turn that swaps the players. An extra bridge never hurts the player who owns it. And the game cannot end drawn, because at the end exactly one of a blue route and a red route exists — which is the fact about the plane two sections above, and is Bridg-It’s version of the no-draw theorem Hex is built on. Those three are exactly the hypotheses of strategy stealing, and strategy stealing then says the first player wins, in four lines, naming no move.

The count says the same thing and does name moves. Here the comparison between an argument that names no move and a criterion with a certificate is sharper than for any other game in these essays, because both apply to the same board and reach the same conclusion. Stealing needs the symmetry and delivers one bit. The trees need the count and deliver a strategy, checkable by anyone handed the two trees — the certificate a strategy is not a certificate says games do not usually have.

On the board of size four the construction names four first moves, all of them across the middle of the board, which is where a Bridg-It player would put a first bridge anyway. The board is past playing out — twenty-five links is far beyond what the solver reaches — so these four are named by the argument alone. What the argument guarantees is that each leaves blue holding two disjoint connected sets with red to move, and that position is a win by the rule played out on smaller graphs in the essay before this one.

There is a third known answer, and it is a different kind of object again. A pairing strategy for Bridg-It — a first bridge, and then a fixed partner for every bridge red might build — was found by Oliver Gross and published by Martin Gardner. It is the same shape as the strategy that is a symmetry: whatever the opponent does, answer with its pair. The trees are the general version of that pairing, and the pairing is what the trees look like when somebody has taken the trouble to fix them once for a particular board.

The resemblance to the mirror strategy that proves every game has a negative is worth a sentence, because it is a resemblance and not an identity. The mirror answers a move with the same move on the other board, and it works because the two boards are copies. The Bridg-It pairing answers a bridge with a different bridge on the same board, and it works because the pairs are chosen so that no bridge red builds can cut both members of any pair blue relies on. Both are strategies that compute nothing during play, and both put all the thought into a table fixed in advance — which is the sense of solved that what solved means calls a formula naming the move from anywhere.

Where the dual does not exist #

The whole construction needs a drawing, and not every graph has one.

The complete graph on five points cannot be drawn without two links crossing, and it is the graph the earlier essays surveyed most heavily. It has no faces in the required sense, so it has no dual graph, and Cut playing on it is not Short playing on anything that can be drawn. Lehman’s theorem still covers it — his argument is about matroids, and every matroid has a dual matroid whether or not that dual is the cycle structure of some graph — but the dual is then a family of link sets with no picture, and the elegant version of the correspondence, one link crossing one link, is gone.

The marks have to share the outer face. The imaginary link runs round the outside, so A and B must both be on the outside of the drawing. Every graph here is drawn that way, and a graph whose marks sit on two inner faces has to be redrawn — or has no dual in this sense at all, if no drawing puts them together.

And the dual is a statement about the drawing, not only about the graph. A graph with several drawings has several duals, which can differ; they give the same game, since the game only knows which links meet, but the pictures differ. The figures here draw one dual per graph and do not say which drawings would give others.

Nor does play reach far. The survey plays out boards of up to thirteen links. The count reaches size eight by exchange, the trees on size four are drawn from the same packing, and neither is confirmed by search past size three.

The rule this depends on #

The switching game is won by joining two points, not by making the last move, and the duality depends on that twice.

It depends on it once because the identity between the two games is an identity between goals: a route in the graph against a route in the dual, and the plane guarantees exactly one of the two. Under a last-move rule there is no route to speak of and nothing for the plane to adjudicate.

And it depends on it again in the no-draw fact. Hex and Bridg-It end with exactly one winner because a finished board of two colours in the plane cannot contain both connections or neither. That is a theorem about topology, not about play — which is why it holds on every board size at once, and why it is the one hypothesis strategy stealing and the dual construction both borrow.

The surprise: the no-draw theorem and the duality are one fact #

Bridg-It is usually explained in two unrelated steps. First, the game cannot be drawn, which is a remark about the board. Second, the first player wins, which is a remark about strategy.

The dual shows they are the same remark. The reason a finished board has exactly one winner is that a route and a dual route cannot both survive and cannot both fail; the reason Cut’s game is Short’s game on the dual is the same sentence read as a statement about moves. And the reason the first player wins is then a count — one link short of two trees, at every size — which the symmetry of the board forces to come out the same for both players.

What looked like a game with two players and two goals is one game on two graphs, and the board in the box was drawn so that the two graphs are the same.

Still open: claiming points instead of links #

Every game here is played on links. Short secures them, Cut deletes them, and the trees are sets of links.

Hex is played on cells. A stone claims a hexagon, and the hexagons are the points of a graph rather than its links. The switching game played that way — Short claims points, Cut deletes points — is the game Hex is an instance of, and the question it poses is whether anything like the trees survives the change: whether claiming a point has a criterion that counts, or whether moving the game from links to points is exactly the step that takes the criterion away. How hard is it already records where the general version of that game sits among the hard problems; what it does not show is which step of the move from links to points does the damage.