pabloskimg's blog

Proof that if a biconnected component has an odd simple cycle, then ALL edges in such component belong to some odd simple cycle?
By pabloskimg, history, 7 years ago, In English

Is it true that if a biconnected component has an odd simple cycle, then ALL edges in that component belong to some (not necessarily the same) odd simple cycle? If that's the case, what would be a formal proof for that? I believe this property would be crucial to solve this problem: http://mirror.codeforces.com/problemset/problem/97/E

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Yes, it's true.

Imagine you have a cycle of odd length which covers vertices (a1, a2, ..., a2k + 1). Then imagine a edge. If the edge is (u, v) we can simply pick any path from u to any vertex in the cycle a. Then go through the cycle and get back to this vertex. Finally go from this vertex in the cycle to u by the same path, you chose earlier. What will be the parity of the length of this cycle?

Well the length is 2k + 1 (odd) plus 2 * (the length of the path from u to the cycle). This number obviously will be always odd as it is sum of an odd number and even (because we have 2*).

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I didn't quite understand your proof. You said you go from u to some arbitrary node a in the odd cycle, but what if this path (u -> a) partially overlaps with the cycle? And then you say you go back from a to u using the same path backwards. But that would not be a simple cycle, because you would be repeating nodes. Moreover, you didn't mention the node v, but remember you want to prove that the edge (u,v) belongs to an odd length cycle.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well you didn't write that the cycle should be simple.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Good point, I guess I should update the title then.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I go over the proof in this video for a different problem: https://www.youtube.com/watch?v=tRTezLvPZ3k

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the video. Do I need to watch it all or can I skip to the proof part?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can skip right to the proof part at the end

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok, I just reviewed the proof and it makes sense except for the fact that you are assuming that your paths I1 and I2 from the external node to the odd cycle are disjoint. Why can we make such assumption?

        → Reply