Snarks, Hypohamiltonian Graphs and Non-Supereulerian Graphs

A graph  G  is hypohamiltonian if it is not Hamiltonian but for each  v ∈ V ( G ) v∈V(G), the graph  G − v G−v is Hamiltonian. A graph is supereulerian if it has a spanning Eulerian subgraph. A graph  G  is called collapsible if for every even subset  R ⊆ V ( G ) R⊆V(G), there is a spanning connected subgraph  H  of  G  such that  R  is the set of vertices of odd degree in  H . A graph is reduced if it has no nontrivial collapsible subgraphs. In this note, we first prove that all hypohamiltonian cubic graphs are reduced non-supereulerian graphs. Then we introduce an operation to construct graphs from hypohamiltonian cubic graphs such that the resulting graphs are 3-edge-connected non-supereulerian reduced graphs and cannot be contracted to a snark. This disproves two conjectures, one of which was first posed by Catlin et al. in [Congr. Num. 76:173–181,  1990 ] and in [J. Combin. Theory, Ser B 66:123–139,  1996 ], and was posed again by Li et al. in [Acta Math. Sin. English Ser 30(2):291–304,  2014 ] and by Yang in [Supereulerian graphs, hamiltonicity of graphs and several extremal problems in graphs, Ph. D. Dissertation, Université Paris-Sub, September 27,  2013 ], respectively, the other one was posed by Yang  2013 .