In a connected graph, is it correct to say: |V| = O(|E|) ?

My intuition is that in a connected graph, |E| >= |V|-1.

Thank you.

CodePudding user response：

Yes.

Big-oh notation gives an upper bound. For a connected graph we have |E| >= |V|-1 like you said, so |E| is an upper bound for |V| and therefore we can say that |V| = O(|E|).