10.2 Trees, Properties of Spanning Trees & Cayley's Formula

Back to Discrete Mathematics Notes

📚Module 10: Advanced Graph Theory: Trees, Planarity & ColoringTopic 10.2: Trees & Cayley's Formula⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Lean Corporate Org Chart & Cable Television Backbone

Think of trees as the most cost-efficient communication network:

1. The Tree Contract (Zero Redundancy, Zero Islands): Imagine laying fiber-optic cables to connect $n$ offices. If there are any loops, you wasted money buying redundant cables. If there are any disconnected offices, people cannot communicate. A Tree connects all $n$ offices using the absolute minimum possible cables: exactly $n - 1$ cables!
2. The Fragility of a Tree: Because there is zero redundancy:
   • Cutting any single cable splits the network into two disconnected islands (every edge is a bridge).
   • Adding any new cable between two existing offices immediately creates a redundant loop (a cycle).
3. Cayley's Formula & Prüfer Codes: How many different ways can you wire $n$ numbered computers together as a tree? Arthur Cayley proved in 1889 that there are exactly $n^{n - 2}$ distinct labeled trees. Heinz Prüfer created a brilliant loss-less compression algorithm: any tree on $n$ vertices compresses into a unique phone number of length $n - 2$!

💻 Bridging to Computer Science: DOM Trees, ASTs, Spanning Tree Protocol & File Systems

In computer systems:

• Spanning Tree Protocol (STP / IEEE 802.1D): Ethernet switches run STP to dynamically disable redundant bridge ports, preventing devastating broadcast radiation storms by maintaining a loop-free logical spanning tree.
• Compilers & Parsers: Abstract Syntax Trees (ASTs) represent the hierarchical grammatical structure of source code without circular loops.
• Hierarchical File Systems: Unix directory structures form rooted trees where directories branch down to file leaves.

📑Table of Contents

• 🌳 The 6 Equivalent Characterizations of a Tree
• 🌐 Spanning Trees & Fundamental Cycle/Cut-Set Duality
• 🔢 Cayley's Tree Formula & Prüfer Sequences
• 📝 Step-by-Step Worked Examples
  • Example 1: Constructing the Prüfer Sequence of a Labeled Tree
  • Example 2: Counting Labeled Trees with Specific Vertex Degrees
• 🎯 Exam & Interview Pitfall Check

---

🌳 The 6 Equivalent Characterizations of a Tree

A tree is one of the most mathematically overdetermined structures in computer science.

📖Definition 10.3: Tree and Forestdefinition

1. Tree: An undirected graph is a Tree if and only if it is connected and acyclic (contains no simple cycles).
2. Forest: An undirected graph is a Forest if and only if it is acyclic. Each connected component of a forest is a tree.
   • If a forest has $n$ vertices and $k$ connected components, the total number of edges is: $$|E| = n - k$$

The 6 Equivalent Axiomatic Characterizations of a Tree

Proving any ONE of these properties automatically proves all other five

🌲

1. Connected & Acyclic

Standard Definition

• G is connected and contains zero simple cycles.
• The classical baseline definition of a tree.

⚖️

2. Connected with n - 1 Edges

Edge Budget

• G is connected and |E| = |V| - 1.
• The minimal edge count required for any graph to remain connected.

🚫

3. Acyclic with n - 1 Edges

Cycle-Free Budget

• G has no cycles and |E| = |V| - 1.
• Forces all components to merge into a single connected entity.

🎯

4. Unique Simple Path

Deterministic Routing

• There exists EXACTLY ONE unique simple path between every pair of vertices.
• Zero detours, zero alternative routes.

🌉

5. Minimally Connected

All-Bridge Network

• G is connected, but removing ANY edge e disconnects G: c(G - e) = 2.
• Every single edge in a tree is an articulation bridge!

🔄

6. Maximally Acyclic

Saturated Loop-Free

• G has no cycles, but adding ANY edge between non-adjacent vertices creates a unique cycle.

📐Theorem 10.4: The Leaf (Pendant Vertex) Invarianttheorem

Every tree $T$ with $n \ge 2$ vertices contains at least TWO leaves (vertices of degree 1)!

Proof by Handshaking Lemma: Suppose for contradiction that a tree $T$ with $n \ge 2$ vertices has at most 1 leaf.

• A connected graph with $n \ge 2$ vertices cannot have any isolated vertices ($\deg(v) \ge 1$ for all $v$).
• If there is at most 1 leaf, then at least $n - 1$ vertices must have degree $\ge 2$: $$\sum_{v \in V} \deg(v) \ge 1 + (n - 1) \cdot 2 = 1 + 2n - 2 = 2n - 1$$
• But by the Handshaking Lemma, for any tree with $|E| = n - 1$: $$\sum_{v \in V} \deg(v) = 2 |E| = 2(n - 1) = 2n - 2$$
• This yields $2n - 1 \le 2n - 2 \implies -1 \le -2$, an impossible contradiction! Therefore, every tree with $n \ge 2$ vertices must contain at least two vertices of degree 1.

---

🌐 Spanning Trees & Fundamental Cycle/Cut-Set Duality

📖Definition 10.4: Spanning Tree & Chordsdefinition

Let $G = (V, E)$ be a connected graph:

1. A Spanning Tree $T = (V, E_T)$ of $G$ is a subgraph that is a tree containing all vertices of $G$.
   • Number of tree branches: $|E_T| = n - 1$.
2. Chords (Co-Tree Edges): The remaining edges in $G$ that do not belong to $T$: $$E_{\text{chords}} = E \setminus E_T$$
   • Number of chords: $\mu(G) = |E| - |V| + 1$ (also called the Circuit Rank or Cyclomatic Number of $G$).

📐Theorem 10.5: Fundamental Cycles and Cut-Setstheorem

1. Fundamental Cycle: Adding any single chord edge $e \in E \setminus E_T$ to a spanning tree $T$ creates exactly one unique simple cycle. The collection of cycles formed by adding each chord independently forms the basis of all cycles in $G$. Total fundamental cycles = $|E| - |V| + 1$.
2. Fundamental Cut-Set: Removing any single tree branch $b \in E_T$ splits $T$ into two disconnected trees ($T_1$ and $T_2$). The set of all edges in $G$ connecting $T_1$ and $T_2$ forms a fundamental cut-set. Total fundamental cut-sets = $|V| - 1$.

★ Spanning Tree Branches (4) & Chords (2)

Spanning Tree T (solid green branches) with 4 edges, and Co-Tree chords (dashed amber) with μ(G) = 6 - 5 + 1 = 2 fundamental cycles.

---

🔢 Cayley's Tree Formula & Prüfer Sequences

How many distinct labeled trees can be constructed on $n$ vertices?

📐Theorem 10.6: Cayley's Formula (1889)theorem

The number of distinct labeled trees on $n$ vertices (or the number of spanning trees of the complete graph $K_n$) is:

$$T(n) = n^{n - 2}$$

• For $n = 1$: $1^{1 - 2} = 1^{-1} = 1$ tree.
• For $n = 2$: $2^{2 - 2} = 2^0 = 1$ tree.
• For $n = 3$: $3^{3 - 2} = 3^1 = 3$ trees.
• For $n = 4$: $4^{4 - 2} = 4^2 = 16$ trees.
• For $n = 5$: $5^{5 - 2} = 5^3 = 125$ trees.

Architecture Flow

The Prüfer Sequence Bijection Pipeline

Lossless 1-to-1 mapping between labeled trees on n vertices and sequences of length n - 2

🔍Step 1

Identify Smallest Leaf

Find the leaf vertex v (degree = 1) with the smallest numerical label.

→

Record Neighbor

📝Step 2

Record Neighbor & Delete

Append the label of v's unique neighbor to the Prüfer sequence. Delete vertex v and its incident edge.

→

Repeat Until 2 Vertices Remain

🔢Step 3

Sequence of Length n - 2

Stop when exactly 2 vertices remain. The generated list has length n - 2 with elements from {1, 2, ..., n}.

→

Degree Formula Invariant

⭐Degree Invariant

deg(v) = 1 + count(v)

In the original tree, the degree of vertex v equals 1 plus the number of times v appears in the Prüfer sequence!

---

📝 Step-by-Step Worked Examples

Example 1: Constructing the Prüfer Sequence of a Labeled Tree

Problem Statement: Consider a labeled tree with $n = 6$ vertices $\{1, 2, 3, 4, 5, 6\}$ and edges:

$$\{1, 4\}, \; \{2, 4\}, \; \{3, 4\}, \; \{4, 5\}, \; \{5, 6\}$$

1. Encode this tree into its unique Prüfer sequence.
2. Verify the degree formula $\deg(v) = 1 + \text{count}(v)$.

Step-by-Step Solution:

1. Step 1: Encoding into Prüfer Sequence

   • Initial leaves ($\deg = 1$): $\{1, 2, 3, 6\}$.
   • Smallest leaf is $1$. Its neighbor is $4$.
     • Append $4$ to sequence. Delete leaf $1$.
     • Remaining vertices: $\{2, 3, 4, 5, 6\}$. Sequence: (4).
   • Current leaves: $\{2, 3, 6\}$.
   • Smallest leaf is $2$. Its neighbor is $4$.
     • Append $4$ to sequence. Delete leaf $2$.
     • Remaining vertices: $\{3, 4, 5, 6\}$. Sequence: (4, 4).
   • Current leaves: $\{3, 6\}$.
   • Smallest leaf is $3$. Its neighbor is $4$.
     • Append $4$ to sequence. Delete leaf $3$.
     • Notice: Now vertex $4$ only connects to $5$, so vertex $4$ becomes a leaf!
     • Remaining vertices: $\{4, 5, 6\}$. Sequence: (4, 4, 4).
   • Current leaves: $\{4, 6\}$ (since $\deg(4) = 1, \deg(6) = 1$).
   • Smallest leaf is $4$. Its neighbor is $5$.
     • Append $5$ to sequence. Delete leaf $4$.
     • Remaining vertices: $\{5, 6\}$. Sequence: (4, 4, 4, 5).
   • Exactly $2$ vertices remain ($\{5, 6\}$). We halt!
   • Final Prüfer Sequence: (4, 4, 4, 5) (Length = $6 - 2 = 4$).

2. Step 2: Verify the Degree Formula

   • Sequence: (4, 4, 4, 5).
   • Frequency of vertex $1$: $0 \implies \deg(1) = 1 + 0 = 1$. (Leaf!).
   • Frequency of vertex $2$: $0 \implies \deg(2) = 1 + 0 = 1$. (Leaf!).
   • Frequency of vertex $3$: $0 \implies \deg(3) = 1 + 0 = 1$. (Leaf!).
   • Frequency of vertex $4$: $3 \implies \deg(4) = 1 + 3 = 4$.
   • Frequency of vertex $5$: $1 \implies \deg(5) = 1 + 1 = 2$.
   • Frequency of vertex $6$: $0 \implies \deg(6) = 1 + 0 = 1$. (Leaf!).
   • Original degrees match the tree edges perfectly!

Key Takeaway: Leaves are vertices that never appear in the Prüfer sequence, while high-degree hub vertices appear repeatedly.

---

Example 2: Counting Labeled Trees with Specific Vertex Degrees

Problem Statement: How many labeled trees on $n = 5$ vertices $\{1, 2, 3, 4, 5\}$ exist such that vertex $1$ has degree 3?

Step-by-Step Solution:

1. Step 1: Relate Degree to Prüfer Frequency

   • By the degree invariant: $$\deg(v) = 1 + \text{count}(v) \implies \text{count}(v) = \deg(v) - 1$$
   • Since $\deg(1) = 3$, vertex $1$ must appear exactly: $$\text{count}(1) = 3 - 1 = 2 \text{ times}$$ in the Prüfer sequence of length $n - 2 = 5 - 2 = 3$.

2. Step 2: Combinatorial Choice of Positions and Fillers

   • The Prüfer sequence has $3$ open slots: (_ , _ , _).
   • Number of ways to choose which $2$ slots contain the label $1$: $$\binom{3}{2} = 3 \text{ ways}$$
   • The remaining $1$ slot must be filled by any of the other $4$ vertex labels ($\{2, 3, 4, 5\}$): $$4^1 = 4 \text{ choices}$$
   • Total valid Prüfer sequences: $$\text{Total Trees} = \binom{3}{2} \times 4 = 3 \times 4 = 12 \text{ labeled trees}$$

Key Takeaway: To count trees with specified vertex degrees, use the multinomial distribution over the $n - 2$ slots of the Prüfer code!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If a graph has $n$ vertices and $n - 1$ edges, is it guaranteed to be a tree? Key Focus Points: No! A graph with $n$ vertices and $n - 1$ edges is only a tree if it is connected (or acyclic). If it is disconnected, it could consist of a triangle ($C_3$, 3 vertices, 3 edges) and an isolated vertex ($K_1$, 1 vertex, 0 edges). Total vertices = 4, total edges = 3 ($n - 1$), but it has a cycle and is disconnected! Both conditions ($n - 1$ edges AND connected/acyclic) are strictly required.

Question 2: How many edges must be deleted from a connected graph $G = (V, E)$ to produce a spanning tree? Key Focus Points: A spanning tree strictly requires $n - 1$ edges. Therefore, you must delete exactly:

$$\text{Deleted Edges} = |E| - (n - 1) = |E| - |V| + 1$$

This quantity is the Cyclomatic Number (Circuit Rank) of the graph, representing the exact number of independent cycles in $G$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting that Cayley's formula $n^{n-2}$ applies ONLY to labeled trees Why it fails: $n^{n-2}$ counts labeled trees (where vertices are numbered 1 to $n$). For unlabeled trees (isomorphism classes), the counts are much smaller: for $n = 4$, there are 16 labeled trees, but only 2 unlabeled trees (the star graph $K_{1, 3}$ and the path graph $P_4$).

Trap 2: Assuming every edge in a general graph is a bridge Why it fails: In a general graph with cycles, edges belonging to cycles are not bridges. Only in a tree is every single edge guaranteed to be a bridge!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic10.1 Eulerian vs Hamiltonian Graphs: Existence Theorems & CharacterizationsNext Topic →10.3 Planar Graphs, Euler's Polyhedral Formula & Kuratowski's Non-Planar Minors