Is this true: any bipartite graph with unbalanced vertex parity is not Hamiltonian?

Solution 1:

A bipartite graph has unbalanced parity if the two vertex sets are not the same size. Such a graph cannot be Hamiltonian, because a Hamilton circuit must alternate between the two vertex sets.

Added: A bit of searching turned up Grinberg’s theorem, which gives a necessary condition for a graph to be Hamiltonian and hence a sufficient condition for a graph to be non-Hamiltonian. This paper might be of use, but I know nothing about it beyond the title. This answer on CSTheory.SE gives another necessary condition for Hamiltonicity and hence sufficient condition for non-Hamiltonicity.