Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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 :)