The number of leaves

Task number: 4215

Prove that if there is a vertex of degree \( k \) in a finite tree, then the tree has at least \( k \) leaves.

  • Solution

    For \( k \le 1 \) the statement holds, so consider \( k \ge 2 \) and a vertex \( v \) of this degree.

    Repeat \( k \) times the following operation. Removing an edge from \( v \) creates two components. One of these components does not contain \( v \). This component is a tree, so it is either a single vertex that was itself a leaf before the edge was removed, or this tree has some edges and in this case contains at least two leaves. At most one of these leaves could be a neighbor \( v \), the others were leaves even before the edge was removed.

    We found at least one leaf behind each edge removed, so the tree must have at least \( k \) leaves.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email