The lecture note by Jeff Erickson discusses Evasive Graph Properties: We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether an (undirected) graph has that property.As an example, it shows that connectivity is evasive.I want to know: Is acyclicity evasive? How to prove/disprove it?My attempt: A rather straightforward adaptation I made from the proof for connectivity does not work for acyclicity.
Evasiveness of acyclicity of undirected graph
algorithms;graph theory;lower bounds
Consider any algorithm for acyclicity. We will use the following adversary:Whenever the algorithm asks for an edge, say that the edge exists if it connects two different connected components. (That is, if it doesn't close a cycle.)You can show that the graph constructed by this dialog is always a forest, and moreover the constructed graph has the same connected components as the query graph (which contains all queried edges). In particular, when the last edge is asked, the graph is a tree (assuming $n \geq 3$; otherwise every graph is acyclic), and the graph is acyclic if and only if this edge does not belong to the graph.