连通图中顶点数V与边数E的Big O关系：|V|=O(|E|)是否成立？

你的直观认知完全正确：连通图的边数满足|E| ≥ |V|-1（树是边数最少的连通图，刚好取等号）。基于这个结论，我们可以直接推导|V|=O(|E|)的正确性：

大O记号的核心定义是：若存在常数C和阈值N₀，当|E|≥N₀时，|V| ≤ C·|E|，则称|V|=O(|E|)。

结合连通图的边数下界：

• 当|E|≥1（对应连通图至少2个顶点），由|E|≥|V|-1可得|V| ≤ |E|+1。
• 取C=2，当|E|≥1时，|E|+1 ≤ 2|E|（因为|E|≥1时，|E|≥1，所以|E|+1 ≤ |E|+|E|=2|E|）。

这就满足了大O的定义，因此**|V|=O(|E|)在连通图中是正确的表述**。

补充说明：即使是边数远多于顶点数的连通图（比如完全图），|V|的增长速度远慢于|E|，显然也满足|V|=O(|E|)（因为更慢的增长量级包含在更快的量级里）。

内容的提问来源于stack exchange，提问作者Toffe1369