A platypus graph is a nonhamiltonian graph for which deletion of any vertex produces a subgraph that is traceable.
No complete bipartite graph or 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).
