Math 2.0

Combinatorics Lemma

Every finite tree with at least two vertices has a leaf

Builds on Degree of a vertexTree

Statement

Let TT be a finite tree with at least two vertices. Then TT has a vertex of degree 11.

Remarks

In fact TT has at least two leaves: the two ends of a longest path are leaves. Proof idea: take a longest path v0,…,vkv_0, \dots, v_k. A neighbour of vkv_k other than vk−1v_{k-1} would extend the path or close a cycle, so deg⁡(vk)=1\deg(v_k) = 1. The lemma is the base of induction proofs on trees, as in the proof that a tree on n vertices has n − 1 edges.

Reading path

To understand this page from the ground up, read these 12 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionWalk, definition, no evidence levelWalkdefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionReachability, definition, no evidence levelReachabilitydefinitionTrail, definition, no evidence levelTraildefinitionConnected graph, definition, no evidence levelConnected graphdefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionAcyclic graph, definition, no evidence levelAcyclic graphdefinitionTree, definition, no evidence levelTreedefinitionEvery finite tree with at least two vertices has a leaf, statement, no evidence levelEvery finite tree wit…statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Walk definition
  4. Degree of a vertex definition
  5. Reachability definition
  6. Trail definition
  7. Connected graph definition
  8. Circuit definition
  9. Cycle definition
  10. Acyclic graph definition
  11. Tree definition
  12. Every finite tree with at least two vertices has a leaf statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Tree_(graph_theory), Properties
About this page
Tag0H8Q4MANBD
URIm2://0H8Q4MANBD
Kindstatement, lemma
WritingW0 stub
MSC05C05
StatusThis copy of the site has no build data. Run m2 status 0H8Q4MANBD.
UsesDegree of a vertex, Tree

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.