Elusive properties of countably infinite graphs

Márton Elekes, Tamás Kátay, Anett Kocsis

A graph property is elusive (or evasive) if any algorithm testing it by asking questions of the form ''Is there an edge between vertices x and y?'' must, in the worst case, examine…