12.3

Let L be the number of leaves of the input tree T.

1. Collect the leaves in an arbitrary order    l₁, l₂, …, l_L (this takes Θ(n) time).
2. Add the edges    (l₁, l₂), (l₂, l₃), …, (l_L-1, l_L) – exactly L − 1 new edges.
3. Let p be the (unique) neighbour of l₁ in T.    The closed walk    l₁ – l₂ – … – l_L – p – l₁    uses every vertex of T exactly once, so it is a Hamiltonian cycle; hence the augmented graph is Hamiltonian.

Optimality.
• Every leaf needs one extra incident edge to raise its degree from 1 to 2; an added edge can help at most two leaves, so any solution needs at least ⌈L / 2⌉ new edges.
• In a Hamiltonian cycle an internal vertex can keep at most two of its original incident tree-edges. Counting the edges that must consequently be discarded shows that at least L − 1 edges have to be inserted. (For a star this lower bound is tight.)
• Steps 1–2 insert exactly L − 1 edges, meeting the lower bound, so the algorithm is optimal.

Pseudocode (Θ(n) overall):

HamiltonianCompletion(T):
  L ← listLeaves(T) # Θ(n)
  E_new ← ∅
  for i = 1 to |L|-1:
    addEdge(L[i], L[i+1]) # store in E_new
  return E_new # |E_new| = L-1

Back to Chapter 12