--- 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-09-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 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) - [Proof by Induction and Strong Induction](https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC) ## Opens up - [Euler Trails and Hamilton Cycles](https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt)