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