# Clarification about a statement in Graph Theory

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

• 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

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

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.

• 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