Vital1ty's blog

condition for eulerian and hamiltonian circuit
By Vital1ty, 10 years ago, In English

Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??

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

»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

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

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

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

        OK, thanks ;)

        If it's really the case, the presented solution is of course OK :)

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

    Thnx :)

    → Reply