running time of Bellman-Ford for a connected graph.

Question

The running time of Bellman-Ford for a directed graph $G$ is $\mathcal O(nm)$, where $n$ is the number of vertices and $m$ the number of edges. If $G$ is a connected graph, is the running time $\mathcal O(m^2)$? I would say yes, because $G$ connected means $m\geq n-1 \Rightarrow n\leq m+1$ so I get $\mathcal O(mn)\subseteq \mathcal O(m(m+1))=\mathcal O(m^2)$. Is this correct?

Answer 1

Yes. Your reasoning is correct.