  A graph property is said to be elusive ( evasive) if every algorithm testing
this property by asking questions of the form "is there an edge between
vertices x and y" requires, in the worst case, to ask about all pairs of
vertices.
  The unsettled Aanderaa-Karp-Rosenberg conjecture is that every monotone graph
property is elusive for finite vertex sets.
  We show that the situation is completely different for infinite vertex sets:
the monotone graph properties "every vertex has degree at least n" and "every
connected components has size at least n" where n is a natural number, are not
elusive for infinite vertex sets, but the monotone graph property "the graph
contains a cycle" is elusive for arbitrary vertex sets. On the other hand, we
also prove that every algorithm testing some natural monotone graph properties,
e.g "every vertex has degree at least n" or "connected" on the vertex set omega
should check "lots of edges", more precisely, all the edges of an infinite
complete subgraph.
