3
$\begingroup$

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

  • 0
    Cited from [here](http://math.stackexchange.com/a/130528/19341): *A lot of sufficient conditions for Hamiltonian graphs are [surveyed here.](http://www.rose-hulman.edu/mathjournal/archives/2000/vol1-n1/paper4/v1n1-4pd.PDF)*2012-04-22

3 Answers 3

11

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.

  • 1
    +1 for a good answer :)2012-04-22
3

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$.

2

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.

  • 0
    Also, if it is combinatorics that you study - don't let this sentence bother you, it is related to computer scince theory called computability theory2012-04-22