Halin graph

Construction

This note is under construction.

Link

This note lacks links.

Citation

This note lacks citations.

In graph theory, a Halin graph ^[1] $H=T\cup C$ is formed from a tree $T$ with at least four vertices and no vertex of degree $2$, embedded in the plane, together with a cycle $C$ connecting the leaves of $T$ in the cyclic order fixed by the embedding.

Lemma 1

Every Halin graph has a Hamiltonian cycle through all its vertices.

Lemma 2

Every Halin graph is minimally 3-connected.

TODO

---

• Halin graphs can be recognized in linear time.
• Halin graphs have low treewidth, many computational problems that are hard on other kinds of planar graphs, such as finding Hamiltonian cycles, can be solved quickly on Halin graphs.
• Every Halin graph that is not a wheel contains at least two fans, and distinct fans are vertex-disjoint.

In graph theory, a Halin graph ^[1][2] is a planar graph constructed from a tree by connecting its leaves, in the cyclic order induced by a planar embedding, into a single cycle. Halin graphs are named after Rudolf Halin.

Definition

---

Definition 1 (Halin graph)

Let $T$ be a tree satisfying $\mathrm{deg}(v)\ne 2$ for every vertex $v\in T$ and possessing at least three leaves, together with a fixed planar embedding of $T$. Let $C$ denote the cycle obtained by joining the leaves of $T$ according to the cyclic order induced by this embedding. The Halin graph is defined as the graph $H=T\cup C$.

Definition 2 (Skeleton and adjoint cycle)

Given a Halin graph $H=T\cup C$ as in Definition 1, the tree $T$ is referred to as the skeleton (or characteristic tree) of $H$, and the cycle $C$ is referred to as its adjoint cycle. The vertices of $H$ lying on $C$ coincide with the leaves of $T$; the remaining vertices of $H$ are the internal vertices of $T$.

Properties

---

TODO

This note has things to do.

• Split the lemma for planarity and 3-connectivity into two lemmas.

Lemma 1 (Planarity and 3-connectivity)

Every Halin graph $H=T\cup C$ is planar and 3-connected.

Proof of Lemma 1

Planarity follows directly from the construction: $T$ admits a crossing-free embedding by assumption, and $C$ is added along the outer face by connecting consecutive leaves in their cyclic order, so no crossings are introduced. 3-connectivity is established by showing that the removal of any two vertices from $H$ leaves the remaining graph connected. The removal of two vertices lying on $C$ leaves the remaining arcs of $C$ attached to $T$, which remains connected. The removal of an internal vertex of $T$ together with any other vertex cannot disconnect $H$, since the absence of degree-2 vertices in $T$ ensures that every internal vertex is incident to at least three vertex-disjoint paths toward the cycle $C$. A complete case analysis is given in Halin (1971).

Theorem 1 (Hamiltonicity)

Every Halin graph is Hamiltonian.

Proof of Theorem 1

The claim is proved by induction on the number of internal vertices of the skeleton $T$. If $T$ is a star, $H$ is a wheel graph, which is Hamiltonian by virtue of its rim cycle. For the inductive step, let $u$ be an internal vertex of $T$ adjacent to at least two leaves. Contracting the subtree rooted at $u$ into a single leaf yields a smaller Halin graph $H^{\prime }$, which is Hamiltonian by the induction hypothesis. A Hamiltonian cycle of $H^{\prime }$ may then be modified to route through the original leaves adjacent to $u$, yielding a Hamiltonian cycle of $H$. $\square$

Corollary 1 (Uniqueness of the planar embedding)

Every Halin graph admits a combinatorially unique planar embedding, up to the choice of outer face and reflection.

Proof of Corollary 1

This follows from Lemma 1 in conjunction with Whitney's theorem, according to which every 3-connected planar graph admits a unique embedding in the sphere up to reflection.

Examples

---

Example 1 (Wheel graphs)

If the skeleton $T$ is a star $K_{1,k}$ — a single central vertex adjacent to $k\ge 3$ leaves — the resulting Halin graph $T\cup C$ coincides with the wheel graph $W_k$, consisting of the central vertex together with a $k$-cycle through its neighbors.

References

1. [1]

   “Halin graph”, Wikipedia, Available: https://en.wikipedia.org/wiki/Halin_graph, Accessed: 2026-05-25 ↩ ↩²

2. [2]

   “Halin Graph”, Wolfram MathWorld, Available: https://mathworld.wolfram.com/HalinGraph.html, Accessed: 2026-07-14 ↩