Aanderaa–Karp–Rosenberg conjecture for finite graph properties

Let $V$ be a finite vertex set and let a graph property be a property of graphs on $V$ that is invariant under relabeling of the vertices. A graph property is monotone if adding edges preserves the property, and nontrivial if it is true for some graphs on $V$ and false for others. It is elusive if, in the Seeker–Hider edge-query game, Hider has a winning strategy forcing Seeker to query every pair of vertices before determining whether the graph has the property.

Aanderaa–Karp–Rosenberg conjecture. Every nontrivial monotone graph property is elusive.

The conjecture asserts that every nontrivial monotone graph property requires examining all possible vertex pairs in the worst case. It is a long-standing unresolved problem, originating in the 1970s; the paper discusses its failure for infinite vertex sets rather than resolving the classical finite version.