A platypus graph is a nonhamiltonian graph with at least three vertices for which deletion of any vertex produces an induced subgraph that is traceable.
The name alludes to the platypus being an egg-laying mammal and to the similarly hybrid nature of the graph class: every hypohamiltonian graph and every hypotraceable graph is a platypus graph, but there are platypus graphs belonging to neither class (Zamfirescu 2017).
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).
A generalized Petersen graph is platypus iff it is isomorphic
to 
with 
(Alspach 1983, Goedgebeur et al. 2020).
