Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that it works just fine, but I don't really know how to prove its correctness properly. Here is the pseudo-code:

Let s be the root
set parent[s]=s and parent[v]=null for all other v
create queue q ;
while (!isEmpty(q) && !cycle) {
 for every edge (u,v) incident to u {
 if (parent[v]==null){
 else if (parent[u]!=v){
   keep the edge (u,v)
if (cycle){
 print edge (u,v)
 while (parent[u]!=parent[v])&& (parent[v]!=u)&&(parent[u]!=v){
        print edge (u,parent[u]) and  edge (v,parent[v]) 
    if (parent[u]==parent[v])
        print edge (u,parent[u]) and edge (v,parent[v]) 
        print edge (u,v) 

I've been working on the proof but i can't get through it. First i want to prove that if G contains a cycle then the algorithm does detect it. My idea is the following: Let s be the root of the bfs. We know that G contains a cycle, so there is a node such that there are two different paths from s to such a node. Let u be the first node that satisfies this. Since that BFS visits all the nodes, and explores each edge once, and also marks as visited all nodes that were visited, it will reach a step in which it is about to visit the node u for the second time and then it finds the cycle.

Then I want to prove that in the afirmative case, the edges that it prints does forms a cycle, but i'm really stuck with this.


3 Answers 3


I believe your problem has been resolved as this is an old question, but here is a solution just to add up to your knowledge.

Proof of Correctness of BFS

First, two kinds of annoying lemmas. These help us formalize what’s going on as the algorithm is running.

Lemma 1. At end of BFS, for all $v ∈ V$, $\newcommand{\dist}{\operatorname{dist}}\dist(v)$ is at least the distance from $s$ to $v$.

Proof. Will show by induction that at each iteration of loop, this holds for all $v$.

Base Case: 0th iteration.

Inductive Hypothesis: Assume true for the $k$th iteration.

Inductive Case: Consider the vertex $v$ removed from queue on $(k + 1)$st iteration.

  • Only changes $\dist(u)$ for a few vertices, and only if $u$ is adjacent to $v$.
  • For vertices not changed, use IH.
  • Otherwise,
    ∗ distance from $s$ to $v$
    ∗ ≤ distance from $s$ to $u + 1$
    ∗ ≤ $\dist(u)+1$
    ∗ = $\dist(v)$.

Lemma 2. For any $k$, let $(v_1, \dots , v_r)$ be the elements of the queue at iteration $k$. At this iteration,

  1. $\dist(v_1) ≥ \dist(v_r) − 1$
  2. For any $i < j$, $\dist(v_i) < \dist(v_j)$

Proof. Induction

Base Case: Initially, queue is empty.

Inductive Hypothesis: Assume true for $k$th iteration.

Inductive Case: Consider $(k + 1)$st iteration.

  • Remove $v_1$ from queue. New front is $v_2$.
  • Enqueue neighbors of $v_1$.
    ∗ Let $u$ be a neighbor.
    $\dist(u)$ is set to $\dist(v_1) + 1 ≥ \dist(v_r) − 1 + 1 = \dist(v_r)$, so 2. still holds.
    $\dist(v_2) ≥ \dist(v_1) = \dist(u) − 1$, so 1. still holds.

Corollary: Let $v_k$ be the $k$th vertex to have $\dist(v)$ set. $\dist(v_k)$ is increasing in $k$.

Finally, the proof of correctness. At the termination of BFS, if BFS explores $v$, then $\dist(v)$ is the distance from $s$ to $v$.

Proof by contradiction.

  • Assume there’s some vertex with $\dist()$ not equal to the distance from $s$.
  • Let $v$ be such a vertex which is the smallest distance from $s$.
  • Let $u$ be its predecessor on shortest path from $v$ to $u$.
  • By lemma 1, $\dist(v) > $ distance from $s$ to $v$
  • = (distance from $s$ to $u$)$ + 1 = \dist(u) + 1$
  • Consider when $u$ was dequeued. We’ll contradict the above chain of inequalities in any of the three cases:
    – If $v$ wasn’t explored yet, $v$ would have been enqueued with $\dist(v)=\dist(u)+1$. Contradiction to above inequalities.
    – If $v$ is on the queue, then $\operatorname{parent}(v)$ has lower $\dist$ than $u$ does, by corollary to lemma 2. Then $\dist(v) = \dist(\operatorname{parent}(v)) + 1 ≤ \dist(u) + 1$, again contradicting the inequalities.
    – If v has already been dequeued, then $\dist(v) ≤ \dist(u)$. Contradiction again.

Watch the video for clear understanding, along with visual description

  • 2
    $\begingroup$ You had Lemma 16 and Lemma 17. Is this copied from somewhere? If so, you should give proper attribution. $\endgroup$ Commented Apr 12, 2021 at 16:30
  • $\begingroup$ Shouldn't the second point of the lemma 2 be $\text{dist}(v_i)\leq \text{dist}(v_j)$ instead of $\text{dist}(v_i)< \text{dist}(v_j)$? (Otherwise the first point cannot stand true for $r \geq 3$). $\endgroup$
    – Nathaniel
    Commented May 12, 2021 at 22:13

Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle.

Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible distance to $s$. Any two vertices in $S$ can not belong to the same cycle, since then they will form a cycle with a vertex with a smaller depth in the BFS-tree, which contradicts the assumption that they are closest possible to $s$. All these vertices belong to the same level of the BFS-tree since they have the same distance to $s$. The BFS-tree branches at each of them to at least two branches. Sice they all belong to cycles in the graph, there must exist an edge between two branches from the subtree rooted at one of them. This edge has its endpoints between two nodes on the same level in the tree, since else, one of them could have been visited by the other and get a smaller depth. When visiting this edge, our algorithm detects a cycle. The Cycle is hence this edge along with both paths in the BFS-tree from a vertex $v \in S$, to the endpoints of this edge. We output exactly these edges, where we start by printing this edge and backtrack on both branches until we reach back the vertex $v$ .


Theorem (Correctness of BFS)

  • Let G=(V,E) be a directed/undirected graph and suppose BFS is run on it from a given source vertex s∈V.
  • upon termination of the algorithm we should have d[v]=δ(s,v) for all v∈V, where δ(s,v) is the shortest path from s to v. (Note: the main difference between d and δ is that d is distance what the algorithm has calculated and δ is the distance of the actual shortest path from s to v.). This is our Claim

Suppose (the major assumption that drives this correctness),

upon termination, there exists a vertex x such that d[x]≠ δ(s,x).

Here we use the Lemma: upon termination, for each vertex v∈V, the value d[v] computed by BFS satisfies d[v] $\geqq$ $\delta$ (s,v)

Therefre by Lemma, d[x] $\geqq$ δ(s,x).

let there exist many such x's, where d[x] $\gt$ δ(s,x) [d[x]≠ δ(s,x)].

Among such vertices in G, we choose a vertex v in G which the closest vertex to s.

Observe that

  1. v $\neq$ s since d[s]=0=$\delta$(s,s)
  2. v must be reachable from s.

Suppose , v is not reachable from s, then $\delta$(s,v)=$\infty$, by the property of Lemma d[v]>$\delta$(s,v)=$\infty$ which is impossible.

Suppose v is reachable from s and v$\neq$s, there exists a non-trivial shortest path P from s to v. Let u be the vertex immediately preceding v on P.

$\delta$(s,v)=$\delta$(s,u) + 1

Therefore, $\delta$(s,u)<$\delta$(s,v). Then by the choice of v, d[u]=$\delta$(s,u). This implies

d[v]> $\delta$(s,v) = $\delta$(s,u)+1 = d[u]+1

d[v]>d[u]+1 => (1)

Now, Consider the time BFS chooses to dequeue the vertex u from Q. At this time the vertex v is either white, grey or black (undiscovered, discovered or discovered and adjacent vertices added to queue)

[Lemma: Suppose x and y are enqueued in BFS and x is enqueued before y, then d[x]<=d[y] at the time y is enqueued]

Case 1: The vertex v is white

Then, d[v]=d[u]+1 which is contradiction to (1).

Case 2: The vertex v is grey

This means v is already discovered by some other vertex w$\in$V which was dequeued before u,



Thus, d[v]<=d[u]+1 which is a contradiction to (1)

Case 3: the colour of v is black

This means v was discovered before u or v was dequeued before u. Therefore d[v]<=d[u], which is a contradiction.

In all the above three cases, we observe that our assumption d[v]>$\delta$(s,v) is wrong. Thus, no such vertex exits and for all vertex v, d[v]=$\delta$(s,v)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.