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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
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*).
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.
well you didn't write that the cycle should be simple.
Good point, I guess I should update the title then.
Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
I go over the proof in this video for a different problem: https://www.youtube.com/watch?v=tRTezLvPZ3k
Thanks for the video. Do I need to watch it all or can I skip to the proof part?
You can skip right to the proof part at the end
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?