Lower bounds: Detecting a length 2 path

Question

Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.

Answer 1

Suppose the algorithm does less than $\frac{n^2-n}{2}-2(n-1)$ accesses to the matrix, then, there is at least one column (restricted to the upper triangular part of the matrix) such that there are at least two elements the algorithm have never checked.

This can be proved by contradiction, if every column has at most one unchecked element, then the algoritm have done at least $\frac{n^2-n}{2}-(n-1)$, but this contradicts the hypothesis.

Then, supposing every $a_{ij}$ element the algorithm has checked is equal to $0$, whatever the output of the algorithm, it may be wrong. Indeed, if the algorithm sais there are no paths, then, in the "doublely unchecked" column can happen that $a_{ij}=a_{kj}=1$, so there will be a path $i\to j\to k$ whose lenght is two. Otherwise, if the algorithm says there is a path, the matriz could be entirely made of $0$'s.

Note that if the graph is represented with an adjacency list for each vertex the statement does not hold, beacause there is an easy algorithm in $\mathcal{O}(n)$.