A Halin graph, sometimes known as a roofless polyhedron, is a polyhedral graph constructed from a planar embedding
of a tree having four or more vertices, no vertices of degree
two, and constructed by connecting all leaves of the tree with a cycle which passes
around the tree's boundary. 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).
