Consider the problem:
Given an undirected graph and two of its vertices, is there a path between them?
I often read that this problem can be solved in linear time in the number of vertices! I am not sure why this claim holds.
Can this really be done in linear time (not amortized) without preprocessing?