--- title: "Trees and Spanning Trees" description: "Characterise a tree in several equivalent ways, prove the edge count, and count the labelled trees on n vertices." canonical: https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ source: https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Trees and Spanning Trees Characterise a tree in several equivalent ways, prove the edge count, and count the labelled trees on n vertices. Subject: Mathematics · Area: Discrete Mathematics · Ages 20 to 21 Page: https://lightmysky.com/learn/mathematics/trees-and-spanning-trees-mt_kMWpsz44yJ ## Ready when they can - 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 ## Lesson: Trees, spanning trees, and counting them 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. **Example.** 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. **Tip.** 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. **Recap.** Spot a tree by any of its three faces, count edges as vertices minus one, and count labelled trees with Cayley. ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Graphs, Degrees and the Handshake Lemma](https://lightmysky.com/learn/mathematics/graphs-degrees-and-the-handshake-lemma-mt_1oqO_o3bTO) ## Opens up - [Euler Trails and Hamilton Cycles](https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt)