BFS Scans Each Undirected Edge Exactly Twice

Intuition

BFS dequeues each vertex once and then scans that vertex's adjacency list. In an undirected graph the edge $\{u,w\}$ is stored in both $u$'s list and $w$'s list. So while processing $u$ you scan it once, and while processing $w$ you scan it again: each edge is examined exactly twice.

Result / Method

Summing the scan cost over all vertices gives $\sum_u \deg(u) = 2|E|$ edge inspections. Adding the $O(V)$ cost of enqueueing/dequeueing each vertex once yields the textbook bound: $T(n) = \Theta(V+E).$ Note $O(V)$ alone is wrong: for a connected graph $E$ can reach $\binom{n}{2}=\Theta(n^2)$.

Worked example

Graph with edges $\{a,b\},\{a,c\},\{b,c\}$ ($V=3,E=3$):

adj[a] = [b, c]
adj[b] = [a, c]
adj[c] = [a, b]

Edge $\{a,b\}$ is seen in adj[a] and in adj[b] -> 2 times. Same for the other two edges. Total scans $= 6 = 2E$.

Exam trick: "Vertices are visited in order of smallest distance from $v$" sounds true (BFS is level-order), but the order within a level is arbitrary, so it does not pin down the visiting order. The clean, unambiguous fact is that each undirected edge is scanned exactly twice — the very accounting behind $\Theta(V+E)$.