Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs
Since $m \in \Theta(n^2)$ in the worst case, $O$-bounds don't tell you much. That is to say, just from these bounds alone, you can't say that $O(m)$ is better than $O(n^2)$ (and the reverse never holds for simple graphs).

However, if you have $\Theta$-bounds then $\Theta(m)$ is properly better than $\Theta(n^2)$ if $m \in o(n^2)$, i.e. you have sparse graphs.

Also, the usual limitations of $O$-worst-case analysis apply: you may actually be interested in typical-case behaviour, constant factors may matter to you, and you need efficiency for finite (small?) $n$.