On Non‐Hamiltonian Graphs for which every Vertex‐Deleted Subgraph Is Traceable

We call a graph G a platypus if G is non‐hamiltonian, and for any vertex v in G, the graph is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypohamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of Wiener. We also prove that there exists a k‐connected platypus for every .