Cayley Trees and k-Regular Trees

Cayley Trees and $k$-Regular Trees#

A tree is a connected acyclic graph. Trees are the simplest connected structures and appear throughout combinatorics, statistical mechanics, and network theory. This notebook covers:

Cayley’s formula: counting labeled trees on $n$ vertices.
Prüfer sequences: a bijective encoding of labeled trees.
$k$-regular trees / Bethe lattices: infinite trees where every node has the same degree.

Labeled Trees and Cayley’s Formula#

Definition. A labeled tree on $[n] = \{1, \ldots, n\}$ is a tree whose vertex set is exactly $[n]$. Let $\mathcal{T}_n$ denote the set of all such trees.

Theorem (Cayley 1889). $$|\mathcal{T}_n| = n^{n-2}$$

The first few values: $|\mathcal{T}_1| = 1$, $|\mathcal{T}_2| = 1$, $|\mathcal{T}_3| = 3$, $|\mathcal{T}_4| = 16$, $|\mathcal{T}_5| = 125$.

Corollary. A uniformly random labeled tree on $n$ vertices has expected degree: $$\mathbb{E}[\deg(v)] = \frac{2(n-1)}{n} \to 2 \quad \text{as } n \to \infty$$

and the degree of a fixed vertex $v$ satisfies $\deg(v) - 1 \sim \mathrm{Binomial}(n-2, 1/n) \to \mathrm{Poisson}(1)$.

Prüfer Sequences#

The cleanest proof of Cayley’s formula is via a bijection with Prüfer sequences.

Definition. A Prüfer sequence of length $n-2$ is any sequence $(a_1, a_2, \ldots, a_{n-2}) \in [n]^{n-2}$. There are $n^{n-2}$ such sequences.

Encoding (tree $\to$ sequence). Repeat $n-2$ times:

Find the leaf (degree-1 node) with the smallest label.
Append its unique neighbor to the sequence.
Remove the leaf from the tree.

Decoding (sequence $\to$ tree). Given $(a_1, \ldots, a_{n-2})$:

Compute each node’s degree: $\deg(i) = 1 + |\{j : a_j = i\}|$.
For $k = 1, \ldots, n-2$: find the smallest $i$ with $\deg(i) = 1$, add edge $(i, a_k)$, decrement both degrees.
Add the final edge between the two remaining degree-1 nodes.

This encoding is a bijection, proving $|\mathcal{T}_n| = n^{n-2}$.

$k$-Regular Trees and the Bethe Lattice#

Definition ($k$-regular tree / Bethe lattice). The Bethe lattice $\mathbb{T}_k$ is the unique infinite tree in which every vertex has exactly $k$ neighbors. It has no cycles and infinite diameter.

Growth rate. Fix a root $o$. Let $S_r = \{v : d(v, o) = r\}$ be the sphere of radius $r$.

$|S_0| = 1$
$|S_1| = k$
$|S_r| = k(k-1)^{r-1}$ for $r \geq 1$

The total number of nodes within distance $r$ is: $$|B_r| = 1 + k \sum_{j=0}^{r-1}(k-1)^j = 1 + k\,\frac{(k-1)^r - 1}{k-2}, \qquad k \geq 3$$

This exponential growth (in contrast to $r^d$ for $\mathbb{Z}^d$) makes $\mathbb{T}_k$ a natural mean-field geometry for Ising models and percolation.

Finite approximation. In practice we work with $\mathbb{T}_k^{(d)}$: the subtree of $\mathbb{T}_k$ within distance $d$ of a root. The root has $k$ children, every internal node has $k-1$ children (degree $k$), and leaves have degree $1$.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from collections import Counter

def prufer_encode(tree):
    """
    Encode a labeled tree (nodes labeled 1..n) as a Prufer sequence.
    Returns a list of length n-2.
    """
    T = tree.copy()
    n = T.number_of_nodes()
    sequence = []
    for _ in range(n - 2):
        leaf = min(v for v in T.nodes() if T.degree(v) == 1)
        neighbor = next(iter(T.neighbors(leaf)))
        sequence.append(neighbor)
        T.remove_node(leaf)
    return sequence


def prufer_decode(sequence, n):
    """
    Decode a Prufer sequence back into a labeled tree on vertices 1..n.
    """
    degree = {i: 1 for i in range(1, n + 1)}
    for v in sequence:
        degree[v] += 1

    T = nx.Graph()
    T.add_nodes_from(range(1, n + 1))

    for v in sequence:
        leaf = next(i for i in range(1, n + 1) if degree[i] == 1)
        T.add_edge(leaf, v)
        degree[leaf] -= 1
        degree[v] -= 1

    # Connect the two remaining degree-1 nodes
    remaining = [i for i in range(1, n + 1) if degree[i] == 1]
    T.add_edge(remaining[0], remaining[1])
    return T


# Verify the bijection on a small example
T_orig = nx.random_labeled_tree(6, seed=7)   # random tree on {0,...,5}
# Relabel to 1..n for the Prufer convention
T_orig = nx.relabel_nodes(T_orig, {i: i + 1 for i in range(6)})

seq = prufer_encode(T_orig)
T_decoded = prufer_decode(seq, 6)

print('Prufer sequence:', seq)
print('Original edges: ', sorted(T_orig.edges()))
print('Decoded edges:  ', sorted(T_decoded.edges()))
print('Bijection check (isomorphic as labeled graphs):',
      sorted(T_orig.edges()) == sorted(T_decoded.edges()))

# Verify Cayley's formula: count distinct labeled trees on n nodes
# by enumerating all n^{n-2} Prufer sequences and decoding
from itertools import product

n = 5
trees = set()
for seq in product(range(1, n + 1), repeat=n - 2):
    T = prufer_decode(list(seq), n)
    edge_key = frozenset(frozenset(e) for e in T.edges())
    trees.add(edge_key)

print(f'n = {n}')
print(f'Cayley formula: n^(n-2) = {n**(n-2)}')
print(f'Distinct labeled trees found: {len(trees)}')

def bethe_lattice(k, depth):
    """
    Build a finite approximation of the k-regular Bethe lattice
    up to the given depth from the root.

    Root has k children; every non-leaf internal node has k-1 children
    (so total degree k). Leaves have degree 1.
    """
    G = nx.Graph()
    node_id = 0
    G.add_node(node_id, depth=0)
    queue = [(node_id, 0, k)]          # (node, current_depth, n_children)

    while queue:
        parent, d, n_children = queue.pop(0)
        if d < depth:
            for _ in range(n_children):
                node_id += 1
                G.add_node(node_id, depth=d + 1)
                G.add_edge(parent, node_id)
                # Each child spawns k-1 grandchildren (to maintain degree k)
                queue.append((node_id, d + 1, k - 1))

    return G


k, depth = 3, 4
T_bethe = bethe_lattice(k, depth)

print(f'k={k}, depth={depth}')
print(f'Expected nodes: 1 + {k} * (({k}-1)^{depth} - 1) / ({k}-2) + {k} = {1 + k * ((k-1)**depth - 1) // (k-2) + k}')
print(f'Actual nodes:   {T_bethe.number_of_nodes()}')

# Degree distribution (root and internal nodes have degree k; leaves have degree 1)
deg_counts = Counter(dict(T_bethe.degree()).values())
print('Degree distribution:', dict(sorted(deg_counts.items())))

fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Left: random labeled tree on 10 nodes
T_random = nx.random_labeled_tree(10, seed=42)
T_random = nx.relabel_nodes(T_random, {i: i + 1 for i in range(10)})
pos_r = nx.spring_layout(T_random, seed=42)
nx.draw_networkx(T_random, pos=pos_r, ax=axes[0],
                 node_color='steelblue', node_size=500,
                 edge_color='gray', font_color='white')
axes[0].set_title('Random labeled tree  (n=10)', fontsize=12)
axes[0].axis('off')

# Right: Bethe lattice k=3, depth=3
T_b = bethe_lattice(3, 3)
pos_b = nx.nx_agraph.graphviz_layout(T_b, prog='twopi', root=0) \
    if nx.nx_agraph else nx.spring_layout(T_b, seed=42)
depths = nx.get_node_attributes(T_b, 'depth')
colors = [plt.cm.viridis(d / 3) for d in depths.values()]
nx.draw_networkx(T_b, pos=pos_b, ax=axes[1],
                 node_color=colors, node_size=150,
                 edge_color='gray', with_labels=False, alpha=0.9)
axes[1].set_title('Bethe lattice  (k=3, depth=3)\nColor = distance from root', fontsize=12)
axes[1].axis('off')

plt.tight_layout()
plt.show()

Cayley Trees and k-Regular Trees

Contents

Cayley Trees and \(k\)-Regular Trees#

Labeled Trees and Cayley’s Formula#

Prüfer Sequences#

\(k\)-Regular Trees and the Bethe Lattice#