## Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

In one sense I understand why the bound on BFS and DFS is $$O(|V| + |E|)$$. Every vertex gets considered, hence the $$O(|V|)$$, and over the course of considering all adjacent vertices, we end up considering $$2|E| = O(|E|)$$ vertices total because $$\sum_{v \in V} d_v = 2|E|$$. What I don’t understand is why we even bother specifying $$O(|V| + |E|)$$ in the first place because it seems to me that the tightest bound you can really have in any situation is $$O(|E|)$$. I.e., it seems to me that the $$O(|V|)$$ doesn’t help you at all. To see why, consider two cases:

• The graph is connected. Then of course $$|E| \ge |V – 1|$$.
• The graph isn’t connected. Then you are “stuck” in the connected component you start in. Once again, inside the connected component $$A$$ you start in you have $$|E_A| \ge |V_A – 1|$$. Maybe there are more edges and vertices elsewhere. But once again the $$O(|V|)$$ seems redundant.

Another way I think about it: Adding a vertex alone doesn’t create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $$O(|V|)$$ useful?