Platypus Graph

A platypus graph is a nonhamiltonian graph for which deletion of any vertex produces a subgraph that is traceable.

Following Goedgebeur et al. (2020), the degenerate graph is not counted here as a platypus graph, even though it satisfies the literal vertex-deletion condition under the convention that is traceable.

No connected bipartite graph on at least two vertices with unequal bipartition class sizes is platypus. If the classes have sizes , deleting a vertex from the smaller class gives a bipartite graph with class sizes and , whose sizes differ by at least 2. Such a graph cannot be traceable since any Hamiltonian path in a bipartite graph must alternate between the two bipartition classes.

Consequently, no complete bipartite graph is platypus: unbalanced complete bipartite graphs are ruled out by the preceding observation, balanced is Hamiltonian for , and is excluded by convention. No complete tripartite graph is platypus (E. Weisstein, Jan. 18, 2016).

There are no platypus graphs on 8 or fewer vertices, and the numbers on , 10, ... vertices are given by 4, 48, 814, 24847, ... (OEIS A392591; Goedgebeur et al. 2020). The four platypus graphs on 9 vertices (Zamfirescu 2017, Goedgebeur et al. 2020) are illustrated above in 2- and 3-dimensional embeddings. These 4 graphs are all line graphs that correspond to root graphs of 4 of the 5 of the pathwidth-2 forbidden minors on 9 edges (E. Weisstein, Jan. 17, 2025).

Named platypus graphs include the Barnette-Bosák-Lederberg graph, Celmins-Swart snarks, Coxeter graph, double star snark, flower snarks, Goldberg snarks, Lindgren-Sousselier graphs, Loupekine snarks, Petersen graph, Sousselier graph, 20-, 24-, and 32-Thomassen graphs, Tietze graph, and triangle-replaced Petersen graph.

There exists a cubic platypus of order iff is even and , with the smallest cubic platypus being the Petersen graph (Goedgebeur et al. 2020).

There exists a cubic polyhedral platypus of order iff is even and . Furthermore, all six smallest cubic nonhamiltonian polyhedral graphs are platypuses (Goedgebeur et al. 2020).

A maximally nonhamiltonian graph is a platypus graph iff (Zamfirescu 2017, Goedgebeur et al. 2020), where is the maximum vertex degree and is the vertex count.

The smallest snark which is not a platypus has 32 vertices, and there are exactly thirteen snarks on 32 vertices that are not platypus graphs (Goedgebeur et al. 2020). Furthermore, there exists a platypus snark of order iff or is even and (Goedgebeur et al. 2020).

The -generalized Petersen graph is platypus iff and (Goedgebeur et al. 2020).