A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inGc, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) ≤3/2n forn ≤ 7. We exhibit graphs of even ordern ≥ 36 for which the bound is attained. These graphs are the “snarks”,Jk, of Isaacs and mild variations of them. For oddn ≥ 55 we construct graphs from the graphsJk showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJk, k ≤ 7 are hypohamiltonian cubics with girth 6.
For small values of n it is easily seen that the components of a bigraph on 2n points are themselves bigraphs of their point set.Simmons had asked whether this was always the case and had shown that if a bigraph on 2n points existed which had a component that was not in itself a bigraph then 2n≧16. In this paper we answer his question affirmatively by using a result ofLovász. We also show that any two components of a bigraph intersect.