Why does breadth-first search always find the path with the fewest links?

Put the start in a line. Take from the front, look at its neighbours, and put any neighbour not seen before at the back. On the six-point graph with links a-b, a-c, b-d, c-d, d-e and e-f, start at a. Remove a: b and c are unseen, so both are marked at one link and put in the line as b, c. Remove b: d is unseen, marked at two links, and the line becomes c, d. Remove c: d is already seen, so nothing is added. Remove d: e is unseen, marked at three links. Remove e: f is unseen, marked at four links. Remove f: nothing new. The distances are a at 0, b at 1, c at 1, d at 2, e at 3, f at 4, each one obtained as the distance of the point that reached it plus one. The c-to-d link is the informative one: d was already marked when b looked at it, so c cannot add it a second time. That is not housekeeping for its own sake. It is why d has one distance, 2, rather than two competing distances.

Suppose a point $v$ is first reached at distance $k$, but there is a route to $v$ with $j$ links where $j < k$. Take a point $u$ on that route one step before $v$. The route reaches $u$ in $j-1$ links, so $u$ is at distance at most $j-1$. Since $j-1 < k-1$, every point at distance $j-1$ leaves the line before any point at distance $k-1$ is served. When $u$ leaves the line, every neighbour not yet seen is marked and put at the back, and $v$ is one of those neighbours. So $v$ is marked at distance at most $j$, before the ring at distance $k-1$ is reached. That contradicts $v$ being first reached at $k$. The first arrival is not a lucky one: a shorter route would have forced an earlier arrival.

The natural guess is that the first arrival is shortest because the walk looks tidy when the rings are drawn by hand, with distances appearing in ascending order. Tidiness is not the mechanism. The mechanism is that all points at distance $r$ are taken out of the line before any point at distance $r+1$, so when a point at distance $r$ is taken out, its unseen neighbours are exactly the points that should next be marked at distance $r+1$. If marking is delayed until a point is taken out of the line rather than when it joins, the same point can be put in the line several times by several different neighbours. The printed distances can still come out right, which is the dangerous part, but the line fills with duplicates and the work and memory grow for no gain. The invariant that carries the proof is the placement of the mark, not the shape of the drawing.

The guarantee is exactly and only true when every link counts the same. The line orders points by number of links, not by total cost, so if links carry different costs, a route with fewer links can be more expensive than a route with more links. Then a point reached early by the line may not be reached cheaply, and the first-arrival argument has nothing to stand on. The repair is to serve the cheapest known point next rather than the oldest, which is a priority line instead of a waiting line. The memory picture also changes with scale: the line must hold a whole ring at once, and on a graph where every point has hundreds of neighbours the rings multiply by hundreds each step, so the widest ring, not the number of points, is what limits the walk.