Math 2.0

statement lemma

Every finite tree with at least two vertices has a leaf

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.

Explanations

L1 human

A finite tree with at least one edge always has an end point. Walk along the tree as far as you can without going back. You stop at a vertex with only one edge.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 12 nodes in this order. The foundations come first, and the list ends with this node.

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 node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • 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

Sources

  1. Web https://en.wikipedia.org/wiki/Tree_(graph_theory), Properties

What links here

No node links to this node yet.