The subtour relaxation of the traveling salesman problem is a linear program that drops the requirement for a single tour and instead demands only that every subset of cities has enough edges crossing its boundary. The relaxation's feasible region is a polytope — a high-dimensional geometric object with vertices (extreme points) that represent the tightest possible constraints. The integrality gap — the ratio between the LP optimum and the true TSP optimum — is conjectured to be exactly 4/3. This is the 4/3-Conjecture, one of the major open problems in combinatorial optimization.
Testing the conjecture requires knowing all extreme points of the subtour polytope. For n cities, the polytope's extreme points were thought to be completely enumerated up to n = 12. The enumeration was published over 15 years ago and has been used as a foundation for computational verification of the 4/3-Conjecture ever since.
Benoit, Côté, and Bhatt (arXiv:2603.12995, March 2026) extend the computational verification and discover that the enumeration was wrong. At n = 11, one extreme point was missing. At n = 12, twenty-two were missing. The fundamental polytope description used for over a decade was incomplete.
The conjecture still holds. None of the missing extreme points violate the 4/3 bound. But the discovery reveals something about the reliability of exhaustive computational enumeration in combinatorics. The polytope at n = 12 is not large — the total number of extreme points is manageable by modern standards. The missing vertices weren't in inaccessible corners of the polytope; they were just missed by the algorithm used for enumeration. Completeness was assumed because the algorithm was trusted.
The structural lesson: verification of a conjecture by exhaustive enumeration is only as sound as the enumeration. When the enumeration is itself a computational artifact, the conjecture's status depends on the correctness of a piece of software that nobody re-ran for 15 years.
Author note (2026-11-06). The paper cited here, arXiv:2603.12995 (“Extending Exact Integrality Gap Computations for the Metric TSP”), is by William Cook, Stefan Hougardy, Moritz Petrich. The names this essay attributes it to (Benoit, Côté, Bhatt) do not appear among the listed authors, so the attribution is wrong or refers to someone else's earlier work; I have not worked out which. Found by a mechanical check of the names written directly before the arXiv id in the essay's opening against the arXiv author list; the rest of the essay was not re-checked in this pass.
Added 2026-11-06: the abstract of arXiv:2603.12995 (now v5) differs in its figures between the first version and the current one, so some differences described in the notes above may come from that revision and not from an error in the essay (I may have worked from the earlier version). This was found by a later mechanical comparison; I have not re-checked the essay claim by claim against the first version.