enter image description here

I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions. For eulerian, I can say that the graph has vertex with odd degree hence not eulerian, but how can I determine if they are hamiltonian or not?

  • $\begingroup$ What is the question? $\endgroup$ – Nathaniel May 11 at 10:59
  • $\begingroup$ @Nathaniel i have editted the title $\endgroup$ – Aragorn May 11 at 11:02
  • 1
    $\begingroup$ @Nathaniel the last sentence seems to be a question. How can Aragorn determine whether a graph is Hamiltonian or not. $\endgroup$ – Pål GD May 11 at 11:03

That's a very good question, and the easy answer is that checking whether a graph is Eulerian is much simpler than checking whether a graph is Hamiltonian. You're diving head-first into the field of complexity theory and the famous question P vs NP. (Further reading: What is the definition of P, NP, NP-complete and NP-hard.)

As you said, a graph is Eulerian if and only if the vertices have even degrees.

For checking if a graph is Hamiltonian, I could give you a "certificate" (or "witness") if it indeed was Hamiltonian. However, there is no anti-certificate, or a certificate for showing that the graph is non-Hamiltonian; Checking if a graph is not Hamiltonian is a co-NP-complete problem.

In fact, we believe that any certificate for non-Hamiltonian-ness needs to be exponentially large.

To answer the question:

  1. Try every permutation of vertices, and if one of the permutations is a cycle, then the graph is Hamiltonian. If so, you get a certificate.
  2. If no permutation was a cycle, the graph is not Hamiltonian. You cannot convince your friends that the graph is non-Hamiltonian without trying all permutations*.

(Ps, using algorithmic techniques (DP) you don't have to try every permutation, but still exponentially many.)

  • $\begingroup$ That means all the graphs here have a cycle and are hamiltonian, I don't need to go through a lot of permuations just to determine if those graphs are hamiltonian. $\endgroup$ – Aragorn May 11 at 11:21
  • 1
    $\begingroup$ Incorrect, you need a cycle through all vertices. What is the permutation of the first graph? $\endgroup$ – Pål GD May 11 at 11:22
  • $\begingroup$ 10c2 is the permutation $\endgroup$ – Aragorn May 11 at 11:26

Indeed, for Eulerian graphs there is a simple characterization, whereas for Hamiltonian graphs one can easily show that a graph is Hamiltonian (by drawing the cycle) but there is no uniform technique to demonstrate the contrary.

For larger graphs it is simply too much work to test every traversal, so we hope for clever ad hoc shortcuts.

As an example, consider your graph to the right. Let us color the top three nodes red and the bottom four nodes green. While there are edges between red nodes, in any Hamiltonian cycle any green node must be between two red nodes. Of course there are only three red nodes, not sufficient to be between the four green nodes. Hence the right graph is not Hamiltonian.

One can generalize this to the following theorem: (see our friends at math.SE)

Let $G$ be a graph. If there exists a set of $k$ nodes in $G$ such that removing these nodes leads to more than $k$ components, then $G$ is not Hamiltonian.

The graph to the left can also be handled in that way (or, directly, the graph is bipartite and the two partitions are not of equal size).

The middle graph, the Petersen graph, is not Hamiltonian either. It seems to need a different approach. Google is your friend.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.