  Pedigree polytopes are extensions of the classical Symmetric Traveling
Salesman Problem polytopes whose graphs (1-skeletons) contain the TSP polytope
graphs as spanning subgraphs. While deciding adjacency of vertices in TSP
polytopes is coNP-complete, Arthanari has given a combinatorial (polynomially
decidable) characterization of adjacency in Pedigree polytopes. Based on this
characterization, we study the graphs of Pedigree polytopes asymptotically, for
large numbers of cities. Unlike TSP polytope graphs, which are vertex
transitive, Pedigree graphs are not even regular. Using an "adjacency game" to
handle Arthanari's intricate inductive characterization of adjacency, we prove
that the minimum degree is asymptotically equal to the number of vertices,
i.e., the graph is "asymptotically almost complete".

Discrete Mathematics;Combinatorics