  Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a
lot of attention. Pedigree polytopes are extensions of the classical Symmetric
Traveling Salesman Problem polytopes (Arthanari 2000) whose graphs contain the
TSP polytope graphs as spanning subgraphs (Arthanari 2013). Unlike TSP
polytopes, Pedigree polytopes are not "symmetric", e.g., their graphs are not
vertex transitive, not even regular. We show that in the graph of the pedigree
polytope, the quotient minimum degree over number of vertices tends to 1 as the
number of cities tends to infinity.
