Plane Triangulations Without a Spanning Halin Subgraph: Counterexamples to the Lovász--Plummer Conjecture on Halin Graphs
Guantao Chen, Hikoe Enomoto, Kenta Ozeki, Shoichi Tsuchiya · SIAM Journal on Discrete Mathematics · 2015
A \sl Halin graph is a simple plane graph consisting of a tree without degree 2 vertices and a cycle induced by the leaves of the tree. In 1975, Lovász and Plummer conjectured that every 4-connected plane triangulation has a spanning Halin subgraph. In this paper, we construct an infinite family of counterexamples to the conjecture.