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.