A sub-Hamiltonian graph is a graph G which is not Hamiltonian and also for every vertex $ u $ where $ u\in V(G) $ the graph $ G-{u}$ is a Hamiltonian graph.
Now can somebody tell me if it is possible to create a sub-Hamiltonian graph with $V(G)\le 16 $ and at least 1 vertex must have degree at least 8?($ \exists u\in V(G),deg(u)\ge8) $
If such graph does not exist, can somebody tell me why?
Let $a$ be a vertex with degree at least $8$. The remaining vertices form a cycle of length at most $15$, so some two adjacent vertices in this cycle must be neighbours of $a$. But then you get a Hamiltonian cycle by inserting $a$ between these two.