A Halin graph, sometimes known as a roofless polyhedron, is a polyhedral graph constructed by taking a planar graph
embedding of a tree having four or more vertices and
no vertices of degree two, then connecting all leaves
of the tree by a graph cycle in their cyclic
order around the embedding. Examples of Halin graphs include the wheel
graph 
,
triangular prism graph 
, and Frucht graph. These
and some other examples of Halin graphs are illustrated above.
The numbers of Halin graphs on 
, 2, ... vertices are 0, 0, 0, 1, 1, 2, 2, 4, 6, 13, 22,
50, 106, 252, ... (OEIS A346779) (E. Weisstein,
Aug. 3-Sep. 29, 2021).
A graph with 
vertices and 
edges is Halin iff it is polyhedral (i.e., planar and 3-connected)
and has a face whose number of vertices equals the circuit
rank 
of the graph.
Halin graphs are Hamiltonian and remain Hamiltonian after any single vertex is deleted (Cornuéjols et al. 1983). Halin graphs have treewidth 3 (Bodlaender 1988), are non-bipartite, and contain a triangle (cycle of order three).
The 
th 
-node Halin graphs are matchstick
for (at least) the following values of 
: (7, 1) (wheel graph 
), (10, 3), (10, 8), (10, 10), (11,
18), (12, 6), (12, 8), (12, 10), (12, 12), (12, 16), (12, 17), (12, 21), (12, 23),
(12, 30), (12, 33), and (12, 34).
Halin graphs are used in the construction of Halin snarks.
