Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What does this statement mean:

"Unlike Eulerian circuits, there is no known necessary and sufficient condition for a graph to be Hamiltonian."

I'm confused about the "no known necessary and sufficient condition " phrase. Thanks

share|improve this question
1  
I think it means a condition $X$ such that a graph is Hamiltonian if and only if $X$ holds. As pointed out by Robert Israel, this is not true, since a definition is trivially such condition. If I were to speculate, it might mean "no simple condition" (with "simple" being the key word that actually can mean anything) or "a condition known to be in $P$" (since we don't know whether $P = NP$). –  dtldarek Apr 22 '12 at 19:03
    
Cited from here: A lot of sufficient conditions for Hamiltonian graphs are surveyed here. –  draks ... Apr 22 '12 at 21:37

3 Answers 3

up vote 10 down vote accepted

As stated, this is simply false: the definition of Hamiltonian is a necessary and sufficient condition. What is true is that there is no known necessary and sufficient condition that is easy to decide: more technically, there is no known decision procedure that runs in polynomial time.

If you're asking what "necessary and sufficient condition" means: a necessary and sufficient condition for $S$ is a statement $C$ that logically equivalent to $S$, i.e. is true whenever $S$ is true, and false whenever $S$ is false. A necessary condition is one that is true whenever $S$ is true. A sufficient condition is one that is false whenever $S$ is false.

share|improve this answer
1  
+1 for a good answer :) –  Belgi Apr 22 '12 at 19:02

A "necessary and sufficient condition" for something means an "if and only if" condition.

More generally, if someone says that $A$ is a sufficient condition for $B$, it means that $A$ implies $B$. (Because in that case, knowing that $A$ true is sufficient to guarantee that $B$ is also true.)

Saying that $A$ is a necessary condition for $B$ means that $B$ implies $A$. (Because then it's necessary for $A$ to be true if you want to have any hope of $B$ being true.)

So saying that $A$ is a necessary and sufficient condition for $B$ just means $A \iff B$.

share|improve this answer

Robert is correct, I would like to add that regardless of this being a 'hard problem' I believe this means that we don't have a 'good' characterizations other than the definition.

share|improve this answer
    
Also, if it is combinatorics that you study - don't let this sentence bother you, it is related to computer scince theory called computability theory –  Belgi Apr 22 '12 at 19:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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