Trees and Spanning Trees
Characterise a tree in several equivalent ways, prove the edge count, and count the labelled trees on n vertices.
What a learner can do afterwards
- Prove that connected with n minus one edges, acyclic and connected, and unique paths are the same condition
- Show every connected graph has a spanning tree
- State Cayley's formula and outline one argument for it
1 · Read
A path is a route along edges that never repeats a vertex. A graph is connected when a path joins every pair of vertices. A cycle is a route that starts and ends at the same vertex, visits at least three different vertices, repeats no vertex except for the start at the end, and never uses the same edge twice. A tree is a connected graph with no cycles. Three descriptions coincide: connected with n minus 1 edges, acyclic and connected, and exactly one path between every pair of vertices. Each viewpoint makes a different fact obvious, so learn to switch between them.
A tree on n vertices always has n minus 1 edges, so a tree with 9 vertices has 8 edges. Adding any missing edge closes exactly one cycle, and removing any edge disconnects the tree.
A spanning tree keeps every vertex while trimming edges to the treelike minimum. Prune cycles one edge at a time and the process always succeeds, so every connected graph has a spanning tree. Networks love them because they connect everything with the fewest edges.
Cayley counted the labelled trees: n to the power (n minus 2) on n vertices. That gives 16 trees on 4 vertices and 125 on 5, so the family grows fast.
Spot a tree by any of its three faces, count edges as vertices minus one, and count labelled trees with Cayley.
More to read
12.10 Trees
A tree is a connected graph with no cycles, the minimal structure that still reaches every vertex. Three descriptions coincide: connected with n minus 1 edges, acyclic and connected, and exactly one path between every pair of vertices. Proving them equivalent is the main work of the topic. Each viewpoint makes a different fact obvious, so learn to switch between them.
12.1 Graph Basics
Graphs model networks with vertices for places and edges for links. Walks, paths, cycles, and degrees give the basic vocabulary. A cycle is a closed walk with no repeats, and its absence defines forests and trees. Counting edges against vertices already hints at the tree formula. These basics support everything about Euler trails and spanning trees.
12.2 Graph Structures
Different drawings can show the same graph, and structure means what survives redrawing. Connected graphs reach every vertex from every other, and components are the disconnected pieces. A spanning tree keeps all vertices while trimming edges to the treelike minimum. Pruning cycles one edge at a time always succeeds, which proves every connected graph has a spanning tree.
12.4 Navigating Graphs
Navigating a graph means finding routes that visit vertices or edges efficiently. Spanning trees give the cheapest way to connect all vertices, which is why networks and road planners love them. Cayley counted the labelled trees: n to the power (n minus 2) on n vertices. Even tiny values like 16 trees on 4 vertices show how fast the family grows.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
This opens up
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.