Tree¶

Definition¶

A tree is a connected undirected network containing no cycles. In the course, a tree can be formed by choosing a subset of the vertices and edges of a larger network.

Interpretation¶

A tree connects its vertices without any redundant edge: there is a route between every two vertices, and no cycle offers a second one. This makes it the basic structure for minimum-cost connection problems.

The five blue edges join all six vertices without a cycle, so they form a tree with $6-1=5$ edges. The dashed edge $A-B$ shows what one more edge does: $A$ and $B$ are already joined through $C$, so it closes the cycle $A-B-C-A$$A$.

A tree sits exactly between two failures: removing any of its edges leaves it no longer connected, and adding any edge between two of its vertices creates a cycle. This is why the Kruskal method rejects every edge that would close a cycle when it builds a spanning tree.

Key Results¶

• A finite tree with $n$ vertices has $n-1$ edges.
• There is exactly one path between any two distinct vertices of a tree.
• A spanning tree additionally includes every vertex of the original network.

Examples¶

• The edges A-B and B-C form a tree on three vertices.
• A tree on 77 vertices has 76 edges, as reinforced by the final-week statements exercise.

Prerequisites¶

• Connected Network
• Cycle

Related Concepts¶

• Spanning Tree
• Minimum Spanning Tree

Sources¶

• OR Modelling · Week 4

Last updated: 20 October 2026 03:02