proof that BFS remains total after adding edge to graph I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).

The inductive proof consists in 2 cases:

(i) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u,v \in G$

(ii) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u \in G, v \not\in G$

I'm stuck at (i).

If I add a new edge $(u,v)$ to $G$, the $BFS$ will remain the same until it reaches $u$ or $v$, then it will add $v$ or $u$ to the queue (where one of them wouldn't be there). I understand that every other member of the queue is there, but there will be one more, so ignoring the fact that there is a new vertex in the queue, the $BFS$ will run in every other vertex just like it should.

How can I show formally that this new vertex in the queue will not interfere in the fact that the $BFS$ is total?
Let us assume that $G$ is a connected undirected finite graph.

Instead of by induction, a direct proof by contradiction as the following is probably easier and clearer.

Suppose we have just finished a BFS starting at vertex $s$. For the sake of contradiction, let us assume that there is a vertex $u$ of $G$ that is unvisited. Because $G$ is connected, there is a path from $s$ to $u$. Select the first unvisited vertex on that path and name it $u'$ (which may or may not be $u$). Let $s'$ be the vertex right before $u'$ on that path (which may or may not be $s$). Then $s'$ must be visited.

Now take a moment to reflect on BFS. Whenever a vertex is visited, each of it adjacent vertices must have been visited earlier or later; I will let you prove this proposition rigorously. However, this contradicts that $s'$, a visited vertex is adjacent to $u'$, an unvisited vertex. Our proof is done.

Here is the summary of the proof strategy. A subset of vertices of a connected graph that is closed under adjacency must contain all vertices. This also holds for infinite graphs.