On Sun, Apr 1, 2012 at 11:32 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Would somebody who knows a little more graph theory than I do please take a look at http://en.wikipedia.org/wiki/Hamiltonian_path and give an opinion?
The section entitled "Bondy–Chvátal theorem" looks to be seriously mangled; in particular, flatly contradicted by the accompanying circuit on a dodecahedron;
I don't see a contradiction. All the vertices of the dodecahedron have degree 3. So deg(u) + deg(v) = 6 < n = 20. So the closure of the dodecahedron is the dodecahedron, and the theorem in this case just says that the dodecahedron is Hamiltonian iff the dodecahedron is Hamiltonian, which is true, though not very interesting. The other two weaker theorems are not contradicted by the dodecahedron, because they are just "if", not "if and only if", so they cannot be contradicted by a Hamiltonian graph like the dodecahedron. Andy