In a sense, I understand why the limit on BFS and DFS is $ O (| V | + | E |) $. Each vertex is considered, hence the $ O (| V |) $, and in the course of considering all adjacent vertices, we end up considering $ 2 | E | = O (| E |) $ total vertices because $ sum_ {v in V} d_v = 2 | E | $. What I don't understand is why we bother to specify $ O (| V | + | E |) $ first of all because it seems to me that the tightest limit you can really have in any situation is $ O (| E |) $. I mean, it seems to me that the $ O (| V |) $ It doesn't help you at all. To see why, consider two cases:

- The graphic is connected. Then of course $ | E | ge | V – 1 | $.
- The graphic is not connected. Then you are "stuck" in the connected component where you start. Again, within the connected component $ A $ you start you have $ | E_A | ge | V_A – 1 | $. Perhaps there are more edges and vertices in other places. But once again the $ O (| V |) $ It seems redundant.

Another way I think about it: adding a vertex alone doesn't create more work since the vertex will simply be floating in space. Add borders can create extra work.

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