Evasiveness of acyclicity of undirected graph

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.

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.

StackExchange Computer Science Q#75683, answer score: 3