1
$\begingroup$

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.

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

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.

Edit: It is also the case that for any DFS tree, any edge not in the tree will be a back edge between nodes in the same branch. Therefore, the question asker's proof is correct.

$\endgroup$
  • $\begingroup$ Since it is an undirected graph, I'm pretty sure they can't be on different branches. $\endgroup$ – Gabi G Nov 17 '18 at 11:13
  • 1
    $\begingroup$ What if G is a tree? $\endgroup$ – helper Nov 17 '18 at 11:14
  • $\begingroup$ 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 $\endgroup$ – Gabi G Nov 17 '18 at 16:28
  • $\begingroup$ 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 $\endgroup$ – Gabi G Nov 17 '18 at 16:40
  • $\begingroup$ Ok, I agree that in any DFS tree, any edge not in the tree will be a back edge in the same branch. I think your proof should either include a proof of this statement, or use my strategy. $\endgroup$ – helper Nov 17 '18 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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