P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference. (warning: possibly erroneous)
Claim: The problem of determining whether a graph is connected is evasive
- evasive as in it requires n C 2 queries i.e checking all the edges
- Prove by making an adversary argument
- Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
- The adversary responds to each query as follows:
- suppose it receives the x th query for 1 <= x <= m
- it considers the graph x defined by taking
- all the responses before this query (those that have reply of 1 => those edges that exist)
- all unqueried edges are set to 1 and hence considered as exist
- the current queried edge is set to 0 and hence not included
- if this graph is still connected without the current edge, then the adversary replies 0, else replies 1
- it's like if the graph does not need the current edge to be fully connected, then return 0
- After all m queries, there are
- responses for previously queried edges, which can be 1 or 0
- one unqueried edge that is unknown
- The adversary makes two graphs using the above information:
- G0: take all edges that are connected according to the responses + set the unqueried edge to 0 (ignore the unknown edge)
- G1: take all edges that are connected according to the responses + set the unqueried edge to 1 (include the unknown edge)
- M cannot distinguish between G0 and G1 because both are consistent with its queries.
- The argument is that G0 is disconnected while G1 is connected, and hence since M can only decide whether the graph is connected or not, M must be wrong for one of the above inputs.
- G1 is connected trivially because it is consistent with the adversary's response strategy.
- If you set the unqueried edges to 1, then the graph must be connected (together with those edges that exist, i.e. previously answered 1)
- G0 is disconnected by contradiction:
- Suppose G0 is connected for purpose of contradiction
- Then let (i, j) = the last unqueried pair of nodes be connected, i.e there is a path between i and j
- Given the adversary strategy, it must replied 1 to all edges on this path, because they exist
- let (i', j') be the edge on this path that was queried last. Then the adversary should have answered 0 as i and j will be set as connected since they are unqueried at that point.
- So a contradiction arises and the assumption is incorrect.
n = 3
Since the algorithm is going to decide whether the graph is connected or not, the adversary simply takes the input that is not consistent with the algorithm.