Key ideas on proving BFS gives the shortest path on unweighted undirected graphs

Basically some gists from http://www.cs.toronto.edu/~krueger/csc263h/lectures/BFS.pdf.

graph TD;
  S-->U;
  U-->V;

$d$: depth from root
$\delta$: shortest path from root

---

Prove by contradiction:
$v$: closest node ( to $s$) where $d[v]\neq \delta(s,v)$.
$u$: the “predecessor” of $d$ on one of the shortest paths from $s$ to $v$.
Statement to contradict with :

• since predecessor, $\delta(s,u)+1=\delta(s,v)$.
• since $v$ closest and $u$ closer, $d[v]=\delta(s,u)$.
• from definition $d[v]\neq \delta(s,v)$.
• therefore $d[v]\neq \delta(s,v)=\delta(s,u)+1$
• since $d[v]$ is some kind of a path, and $\delta(s,v)$ is the shortest path by definition, $d[v]\geq \delta(s,v)$.
• Combine last 2 step and $d[v]>d[u]+1$.

---

Remark: basically deduce that between reaching the predecessor on shortest path and the vertex, the BFS visits at least 2 other nodes.

---

Three cases:

• $v$ not discovered:
  then $d[v]=d[u]+1$ since we will go to $v$ when exploring $u$’s neibours.

• $v$ is discovered and explored:
  Then it is enqued before $u$ thus $d[v]\leq d[u]$¹

• $v$ discovered but not fully explored
  Take the node that discovered $v$, this node is explored before $u$
  so by it is enqueued before $u$¹ $d[w]\leq d[u]$. Since $v$ discovered by $w$, $d[v]=d[w]+1\leq d[u]+1$

  ---

  Remark: the depth difference between $u$ and $v$ can’t be greater than 1 because we would explore all neighbours thus depth difference bettween neightbours cant be greater than $1$; and we know $u$ and $v$ have to be neighbours. Anyway the contradiction proof in other 2 cases uses property¹ but it is pretty intuitive that the depth difference can only be smaller.

---

1. 1.at any time if $v$ is enqueud after $u$ then $d(v)\geq d(u)$ Proof: use induction.↩