Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??
Name |
---|
Consider the graph with n vertices. Hamiltonian circuit contains n edges. So the graph must contain only n edges. And the only way to build hamiltonial graph with n edges is take some permutation of vertices p1, p2, ..., pn and add edges p1 - p2, p2 - p3, ..., pn - 1 - pn, pn - p1. So you should just check the graph to be one big circuit.
If I haven't misunderstood the question and the answer, I think that also K5 (a clique having 5 vertices) is both Hamiltonian and Eulerian. However, it is obviously not a circuit.
// This is "true" also for K2n + 1, n ≥ 2 and many other graphs.
I think you misunderstood it, the question was whether the graph contains a cycle that is both hamiltonian and eulerian, not whether the graph contains both hamiltonian and eulerian cycles.
OK, thanks ;)
If it's really the case, the presented solution is of course OK :)
Thnx :)