I am certainly no graph theorist, but it seems to me the closure of the dodecahedron is the dodecahedron, or am I missing something? This link has a clearer explanation of closure and proof of the Bondy–Chvátal theorem. http://www.cs.ucdavis.edu/~gusfield/cs225w12/Bondy-Chvatal.pdf On Sun, Apr 1, 2012 at 10: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; later theorems appear to have "smaller" substituted for "greater".

 Has a troll been at work, I wonder?

Fred Lunnon

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

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