Logo
All Random Solved Random Open
SOLVED
Does every graph with $n$ vertices and $2n-2$ edges contain a cycle and another vertex adjacent to three vertices on the cycle?
This would be a stronger form of the result of Dirac [Di60] that every such graph contains a subgraph homeomorphic to $K_4$.

The answer is yes, as proved by Thomassen [Th74].

Additional thanks to: Raphael Steiner