# proving correctness of algorithm about graphs with DFS

I need to prove/disprove the correctness of the following algorithm: Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that way. First, you run the DFS algorithm on the graph, since it is connected it will result in a single tree. The for each node $$u$$, you declare the field $$L[u]$$. $$L[u]$$=0 if $$u$$ is the root of the tree, otherwise $$L[u]=L[\pi(u)] + 1$$, when $$\pi(u)$$ is the parent of $$u$$ in the tree.

Finally the algorithm says that: if there exists and edge $$e=$${$$u,v$$} in the original graph $$G$$ so that $$L[u] + L[v]$$ is even than the graph contains and odd cycle. Otherwise (if such edge doesn't exist) the graph doesn't contain an odd cycle.

I am inclined to says that the algorithm is correct. I even have an idea of a proof that uses the idea that if such edge $$e$$ exists, then it must be a back edge in the DFS tree. That would mean there is a cycle and since $$L[v] = L[u] + t$$, where $$t$$ is the number of tree edges in the DFS tree between $$u$$ and $$v$$, I'll get $$2L[u] + t =$$ even number, which means that $$t$$ is even and then with the edge $$e$$ there is an odd cycle.

However, I want to make sure that I am not missing anything, So if some one approve my way or even give an example to disprove the algorithm I would be glad.

• Are you familiar with using DFS to check whether a graph is bipartite? – Yuval Filmus Nov 17 '18 at 2:10
• When you say "$L[u] + L[v]$ is equal", you meant the quantity is "even", right? – helper Nov 17 '18 at 16:30
• yes, my mistake – Gabi G Nov 17 '18 at 16:41

Your algorithm is correct, but I think there's an issue with your proof. The issue is that if $$u$$ and $$v$$ are in different branches of the tree, then their distance would be $$L[u]+L[v]$$, not $$t$$. This quantity is already defined to be even, so your proof only needs to be slightly modified to handle this case.
• If G is a tree then there are only tree edges which means they have to be on the same branch. If you meant the case where $e$ is a tree edge, then $L[u]+L[v]$ will be an odd number – Gabi G Nov 17 '18 at 16:28
• why wouldn't it be $t$? From the way $L[u]$ is declared, it is the distance of $u$ from the root of the DFS tree – Gabi G Nov 17 '18 at 16:40