Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 :)