Chvátal's Condition cannot hold for both a graph and its complement
Alexandr V. Kostochka, Douglas B. West (2006)
Discussiones Mathematicae Graph Theory
Similarity:
Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that or . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.