In graph theory
, a mathematical discipline, a Halin graph
is a planar graph
constructed from a plane embedding of a tree
with at least 4 vertices and with no vertices of degree 2, by connecting all end vertices (i.e., the ones of degree 1) with a cycle
in the natural cyclic order defined by the embedding of the tree.
- It is an edge-minimal planar 3-connected graph.
- It has a unique planar embedding (up to the choice of the outer space; i.e., a unique embedding onto a 2-sphere).
- It is a Hamiltonian graph, moreover, it remains Hamiltonian after deletion of any vertex.