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 
for 
, triangular prism
graph 
,
and Frucht graph. These and some other examples of
Halin graphs are illustrated above.
The numbers of nonisomorphic 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 not bipartite, and contain a triangle (graph cycle of length 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.
