Grinberg’s Criterion Applied to Some Non-Planar Graphs

Abstract

Robertson \(([5])\) and independently, Bondy \(([1])\) proved that the generalized Petersen graph \(P(n, 2)\) is non-hamiltonian if \(n \equiv 5 \pmod{6}\), while Thomason \([7]\) proved that it has precisely \(3\) hamiltonian cycles if \(n \equiv 3 \pmod{6}\). The hamiltonian cycles in the remaining generalized Petersen graphs were enumerated by Schwenk \([6]\). In this note we give a short unified proof of these results using Grinberg’s theorem.