Halin graph

The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called a planar embedding), and the cycle connects the leaves in their clockwise ordering in this embedding.

Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

[2] The cubic Halin graphs – the ones in which each vertex touches exactly three edges – had already been studied over a century earlier by Kirkman.

[4] The graph of a triangular prism is also a Halin graph: it can be drawn so that one of its rectangular faces is the exterior cycle, and the remaining edges form a tree with four leaves, two interior vertices, and five edges.

It is edge-minimal 3-connected, meaning that if any one of its edges is removed, the remaining graph will no longer be 3-connected.

[9] Because every tree without vertices of degree 2 contains two leaves that share the same parent, every Halin graph contains a triangle.

[15] Alternatively, a graph with n vertices and m edges is Halin if and only if it is planar, 3-connected, and has a face whose number of vertices equals the circuit rank m − n + 1 of the graph, all of which can be checked in linear time.

[9][16] This fact was later explained to be a consequence of their low treewidth, and of algorithmic meta-theorems like Courcelle's theorem that provide efficient solutions to these problems on any graph of low treewidth.

The Lovász–Plummer conjecture remained open until 2015, when a construction for infinitely many counterexamples was published.

[23] The Halin graphs are sometimes also called skirted trees[11] or roofless polyhedra.