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?
It is not possible to decide $s$-$t$ connectivity in $O(n)$, in the adjacency matrix model. In fact, here is an $\Omega(n^2)$ lower bound. Let $|S| = |T| = n/2$ be a partition of the vertex set, and choose some $s \in S$ and $t \in T$. Consider the graph in which $S$ and $T$ are both cliques. In this graph $t$ is not reachable from $s$. If we add any edge from $S$ to $T$, then $t$ is reachable from $s$. A simple adversary argument shows that any algorithm that decides where $t$ is reachable from $s$ has to potentially check all $|S| \cdot |T| = n^2/4$ potential edges: if it didn't query some edge $(x,y)$, then it wouldn't be able to distinguish the case in which there is no edge from $S$ to $T$ (and so $t$ is not reachable from $s$) from the case in which $(x,y)$ is the unique edge from $S$ to $T$ (and so $t$ is reachable from $s$).
Your sources are sloppy or you misinterpret something. In general, deciding reachability requires time $\Omega(n+m)$ (assuming adjacency lists). This is linear in the input size (which is in $\Theta(m)$), however, so saying that reachability is solvable in linear time [in input size, which is the default] is correct.
For a proof of this lower bound, see Yuval's answer; the argument remains the same but we conclude that the algorithm must traverse all adjency lists of all nodes in $S$, which contain in total $\Omega(n^2)$ many entries.
Perhaps your source text is dealing with undirected graphs that fulfill some additional structural requirements. For example, for a tree, $m = n - 1$. Therefore, an algorithm that takes $O(n+m)$ time on a general graph actually runs in $O(n)$ time on trees since $n > m$.
