how hard is it

One of the branches of the algorithmic graph theory is a set of problems alike what is the minimum nuber of probes of the adjacency matrix of the graph is required in the worst case, in order to determine whether the graph posseses a given property P.
Of course, the only nontrivial properties are considered.
The upper limit of the probes is the size of adjacency matrix (n(n-1)/2) since the upper diagonal is necessary only.
Bollobas and Eldridge proved that for all nontrivial graph properties the minimum number of probes is \geq 2n-4, linear in the number of vertices of the graph.
A good example of the linear property is existence of a sink node (a node with in-degree=n-1 and out-degree=0) in a directed graph (loop-free).
Smith-Thomas proved that the existence of the sink is in 3n-log n - 3

An elusive property P (evasive property) is a property such that all essential entries of the adjacency matrix must be probed to establish P
Among evasive properties are: beeing a tree, beeing connected, beeing biconnected, beeing planar, beeing k-chromatic

What is a difference between existence of a sink and beeing connected?
Rivest and Vuillemin proved that for every nontrivial, monotone property of graphs, the minimum number of probes is \geq n^2/16
The conjecture that monotone properties are "hard" (evasive) is known as the Aanderaa-Rosenberg conjecture.
Kahn improved Rivest and Vuilemenn result up to n^2/4 for undirected graphs and King improved it to n^2/2 for directed graphs.

See

1. L. Lovasz and N. Young , Lecture Notes on Evasiveness of Graph Properties
2. Graph Algorithms by J. van Leeuwen in Handbook of Theoretical Computer Science, vol. A