Vertices of the Subtour Polytope
William Cook, Stefan Hougardy, and Moritz Petrich, March 2026 
(n=15 updated June 2026).

Let S^n denote the polytope associated with the subtour relaxation 
of the Symmetric Traveling Salesman Problem. 

The files vertices[n].txt contain a complete list of all the vertices of S^n 
for 6 <= n <= 14, which have non-isomorphic weighted support graphs. Note that 
for n <= 5, all the vertices of S^n represent TSP tours. We always include the 
tour (integral vertex). The files half_integral_vertices[n].txt contain all the 
half-integral vertices of S^n for 6 <= n <= 17.

The following table shows the number of (half-integral) vertices for 
a given value of n:

 n     all vertices   half-integral vertices 
 6            2                 2 
 7            3                 3 
 8           13                12
 9           56                42 
10          462               208 
11        4,973             1,023
12       68,342             5,638 
13    1,050,837            31,692 
14   17,672,908           185,644 
15  319,185,400         1,109,906 
16                      6,780,557 
17                     42,134,663 
 

All data files contain comment lines starting with "c". Each other line 
corresponds to a vertex in the format used by Sylvia Boyd 
https://www.site.uottawa.ca/~sylvia/subtourvertices/index.htm 
and is defined as follows:
Let the nodes of the complete graph K_n be labeled 1, 2, 3, ..., n.  In 
these files, each line of text represents a vertex x of S^n, where the 
values of x_e for all edges e of the complete graph K_n are listed in the 
edge order 1-2, 1-3, 1-4, ..., 1-n, 2-3, 2-4, 2-5, ..., 2-n, 3-4, ... etc.

The files vertices13.7z, vertices14.7z, and vertices15.7z are 7-Zip-compressed 
versions of the files vertices13.txt, vertices14.txt, and vertices15.txt. 
7-Zip can be downloaded here: https://7-zip.org/download.html