|
2 | added 6 characters in body | ||
(A hamiltonian graph is a graph that has a cycle passing through every node.) Everyone likes to use this theorem for proving other NP-completeness proofs, but few people would know an actual proof. Even the simplest proof is somewhat messy. The theorem that 3-colorable graphs are NP-complete is similar. |
||||
|
|
1 | [made Community Wiki] | ||
|
Recognizing hamiltonian graphs is NP-complete. (A hamiltonian graph is a graph that has a cycle passing through every node.) Everyone likes to use this theorem for proving other NP-completeness proofs, but few people would know an actual proof. Even the simplest proof is somewhat messy. The theorem that 3-colorable graphs are NP-complete is similar. |
||||
