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?