Two graphs a rule cannot tell apart

Using up the edges instead takes the criterion that decides undirected geography — the first player wins exactly when every maximum matching covers the starting vertex — and asks it about the game where a move uses up the edge it crosses rather than the vertex it leaves. On a graph with no cycle the two games are the same game and the criterion is exact. Once there is a cycle it is not, and it names the winner at 480 of 745 starts.

It ends by proposing a repair, and the proposal is specific. Every failure has one shape: a trail comes back along a cycle to a vertex whose edges are spent. So a rule that read the matching and the cycle might do it — the four-cycle reversing because its length is even, the triangle because its length is odd. And the place to try that is the graphs with exactly one cycle, where there is exactly one thing to read.

There are 21 of them up to six vertices, with 114 starts between them. The question is finite, and the answer is that no rule of that kind exists.

The criterion on one cycle #

77 of 114. On the 14 graphs with no cycle it is right at every start, which is the control rather than a result — with no cycle a trail cannot return to a vertex, so the two games forbid the same moves.

The decline with cycle length is the first thing that makes the proposed repair look plausible. A triangle costs the criterion 15 starts of 64; a four-cycle, 10 of 33; a five-cycle, 6 of 11; a six-cycle, all six. If the cycle’s length is what is going wrong, the cycle’s length ought to be what fixes it.

And the six-cycle row is the sharpest version of that hope. The criterion is wrong at every start of that graph, which is what a rule with a sign error looks like rather than a rule with a gap in it. A reader meeting that row alone would reasonably conclude that the criterion wants reversing on even cycles and go looking for the details.

The rules, scored #

Reversing on even cycles gives 70 of 114, which is worse than doing nothing. Reversing only when the start is on an even cycle gives 75, still worse. Taking the matching on odd cycles and the parity of the edge count on even ones gives 80, which is three better than the criterion and is not a criterion.

The rule that does best is not about cycles. A play in this game is a trail — a walk with no edge repeated — and it ends when the trail cannot be extended, so the winner is decided by whether the final trail has odd length. The shortest maximal trail from the start is odd gets 91 of 114, which is the best on the list and is the one worth pausing on: it is the rule a player would reach for if the opponent were trying to end the game as soon as possible. It is wrong 23 times because the opponent is not trying to do that.

So eleven rules, none exact, and the best reaching four starts in five. That is a measurement about eleven rules, and by itself it is an invitation to think of a twelfth. The threshold was a fact about the census is the warning that goes with scoring rules on a fixed population: a number tuned to one census is a number about that census, and the next section is the reason no twelfth rule is coming.

The pair that closes it #

Two graphs. Each has five vertices and five edges. Each has exactly one cycle and that cycle is a triangle. In each, the start is a vertex of the triangle with degree two, and in each the matching criterion says the second player wins.

In the first the first player wins and in the second the second player does.

Every quantity the proposed repair was going to read is the same across the two: the matching criterion, the cycle’s length, whether the start is on the cycle, how far it is from the cycle, the start’s degree, the number of edges. All six agree, and the winners differ. So there is no rule reading those six quantities that names the winner on the 21 graphs, and the demonstration is two pictures rather than a scan of a rule space.

What actually differs is the shape of what hangs off the triangle. In the first graph the two extra edges are a path — one leaves the triangle and the next leaves that — so a trail that goes out has to come back through the same vertex or stop. In the second they are two separate pendants on two different triangle vertices, so a trail can spend one and reach the other without retracing. That is a fact about the trees attached to the cycle, and no quantity on the list records it.

Every sorting of the starts #

The pair of graphs is one witness, and the same argument run over every sorting is the general statement. Sort the 114 starts into cells by what a rule is allowed to see; a cell holding both a win and a loss is a pair of starts no such rule can separate, and the number of such cells is a lower bound on how wrong every rule of that shape must be.

The matching together with the cycle’s parity gives four cells and all four hold both verdicts, so the best rule reading those two things is right 80 times. Adding whether the start is on the cycle gives eight cells, six ambiguous, best 93. Adding the distance, then the cycle’s actual length, then the degree, then the edge count: 12 cells, 16, 27, 44 — and the ambiguous column runs 6, 5, 5, 7, 6 without ever reaching nought.

Adding detail does not help monotonically, which is the other thing to notice. Going from the cycle’s parity to its length moves the ambiguous count from 6 to 5 and adding the degree moves it back to 7. That is what a set of features unrelated to the answer looks like: finer cells, more of them holding both verdicts, and the best achievable score creeping up only because the cells are getting small enough to memorise the census.

What 91 of 114 is worth #

A rule right at four starts in five is a good heuristic and it is not what the earlier essay was looking for, and the difference is worth stating because the two get confused whenever a measurement is close.

The matching criterion for the vertex game is right at every start of every graph tested, and that is not luck — it is a theorem, and the census is a check on the implementation rather than evidence for the claim. A heuristic that becomes a theorem is the shape a reader hopes for here: a rule observed to work, then proved. What the trail rule has is the first half with no prospect of the second, since the pair of graphs above is already a counterexample to every rule reading the quantities it reads, and the trail rule is wrong on 23 starts of its own.

A rule wrong on 23 of 114 is also not usable as a shortcut, which is the other thing a near-miss can be. A criterion earns its keep by replacing a search, and a rule that replaces a search four times in five leaves the fifth to the search — so the search has to be written anyway, and once it is written the rule saves only the time, on graphs where the search takes microseconds. Three different claims are all called solved separates the senses; this rule is in none of them.

The honest reading of 91 is as a hint about the object. Trails are what the game is about, the matching is what the other game is about, and a rule about trails beating every rule about matchings and cycles says the analogue of the matching theorem, if there is one, is a statement about trails. It does not say which statement, and the two graphs say the obvious candidates are not it.

Why the criterion was never going to extend #

The census is about 21 graphs, and there is a reason of a different kind to stop looking, which belongs on the page because without it the negative result looks like a local accident.

Undirected geography with the vertices used up is decided in polynomial time by the matching criterion — that is the theorem a token on a graph verifies on 41 starts. Undirected geography with the edges used up is not known to be decided in polynomial time by anything, and Fraenkel, Scheinerman and Ullman showed in 1993 that it is complete for the same class as the directed game, which is the class hard, proved is about — and how hard is it sets out what completeness for it means for a game. So a criterion for the general edge game would place a complete problem for that class in polynomial time.

That is a reason about general graphs and it is not a reason about unicyclic ones. A family this restricted could perfectly well have a criterion without anything collapsing — trees do, and the 21 graphs here are trees with one edge added. So the two halves of this page are different evidence and neither replaces the other: the hardness result says no criterion covers every graph, and the census says no rule of the proposed shape covers even the graphs with one cycle.

The second is the one that was worth measuring, because the repair was proposed for exactly that family and a hardness theorem about general graphs would not have refuted it.

What a criterion would have had to be #

It is worth saying what the negative rules out and what it leaves.

It rules out a rule computed from the matching and a handful of numbers about the cycle. That is a statement of the same kind as a strategy is not a certificate makes about proofs — an impossibility about a form of answer rather than about the answer. It does not rule out a different polynomial-time computation on unicyclic graphs — one that walked the attached trees, say, and combined something from each. Nothing here says such a computation does not exist, and the pair of graphs above is exactly the hint about where it would have to look.

Nor does it rule out a criterion of the matching’s own kind on a different object. The matching criterion works because undirected vertex geography is really a question about maximum matchings of the graph, and the natural analogue for the edge game is a question about maximum trails or about matchings of some derived graph. The best rule on the list is a trail rule and it reaches 91 of 114, which is enough to say the trail is the right kind of object and not enough to say which question about it.

Where the impartial theory stops is the general version of the disappointment: a game can be impartial, have ordinary values and still have no way to read one off its position. What the census does settle is that the repair named in advance was the wrong shape, and that is worth a page on its own — a rule proposed on the strength of a pattern in the failures, and the failures turning out to have a cause the pattern did not name.

What the numbers do not say #

Six vertices is the range. There are 21 unicyclic graphs within it and the ambiguity is settled inside it — a pair of graphs a rule cannot separate is a pair whatever else is true — but the rate at which the criterion fails, and the share of each cycle length, are numbers about graphs this small.

The six features are six features. A rule reading something else entirely — the number of leaves, the multiset of tree sizes hanging off the cycle, the parity of the distance from the start to the nearest leaf — is not scored here and is not ruled out by anything on this page. What is ruled out is the family of rules the earlier essay proposed.

And the hardness result is cited rather than reproduced. The reduction behind it is not in these pages and nothing here checks it; what is checked here is the census.

The convention the census is run under #

Normal play: the player who cannot move loses, which for a token on a graph means the player whose turn it is when every edge at the current vertex has been used. A play is a trail from the start and the game ends when the trail is maximal.

The other convention that matters is what a move uses up. In the vertex game a move deletes the vertex it leaves, so the trail cannot revisit any vertex; in the edge game it deletes the edge it crosses, so the trail may revisit a vertex by another edge. That is the whole difference between the two games and it is a difference of one word in the rules — and on a graph with no cycle it is no difference at all, because a trail that revisits a vertex has gone round a cycle.

Both games here are undirected. The directed versions are a separate matter and the directed vertex game is the one whose hardness a token on a graph is about.

The surprise: the failures had a shape and the shape was not a cause #

The repair was proposed because the failures looked organised. They were: a trail returning along a cycle to a spent vertex, with the criterion getting worse as the cycle grew, and every start of the six-cycle wrong. That is a pattern, it is real, and it is in the hero table above.

A pattern in the failures of a rule is not the same as a cause of them, and here it is a symptom shared by cases with different causes. Both graphs in the pair have a triangle, both have a start on it, both have a trail that can come back along the cycle. One of them is a first-player win and the other is not, and what separates them is whether the two edges hanging off the cycle are a path or two pendants — which has nothing to do with the cycle and everything to do with what the trail can do after it leaves.

That is worth carrying into any attempt to patch a criterion from its error table. The error table said cycles, because cycles are what the graphs with errors have in common and what the graphs without them lack. It could not say the arrangement of what hangs off the cycles, because every graph in the failing set has some arrangement and the table does not record which. An error table names what the failures share, and a cause is what the successes lack — and those coincide only when the feature is the cause, which is exactly what is being tested.

Still open: the object the trail rule is about #

The one rule that beats the criterion is about trails, and it is the loosest of the eleven: it assumes the opponent ends the game as fast as possible, which is a strategy rather than a structure. It is right 91 times of 114 anyway.

The measurement that would follow it up is a census of maximal trails rather than of rules: for each start, the multiset of lengths of every maximal trail from it, and whether the winner is a function of that multiset. That is a much richer object than the five numbers tested here and it is still a property of the graph rather than of the play, so a positive answer would be a criterion of the matching’s own kind. A negative one would say the same thing twice and settle where the remaining work is: in the search.