PROVED
This has been solved in the affirmative.
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].
View the LaTeX source
Additional thanks to: Raphael Steiner
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #916, https://www.erdosproblems.com/916, accessed 2025-11-15
