Graph Theory Prove that every tree containing a vertex of de

Graph Theory:

Prove that every tree containing a vertex of degree k contains at least k leaves.

Solution

Answer :

Let vertex v be in a tree G = (V; E ) with degree k.Consider the induced subgraph G₀ by taking out vertex v which is

k connected components, each being a tree.

Formally, G\' = (V - v ,E \' ) where E \' = E - { { v , u } : { u,v } E ,u V }

First note that if any connected component only has 1 vertex, then it was a leaf in G . Consider the connected components that have more than one vertex.

Hence , the connected component has at least 2 leaves. Since in G , it is connected to v so we have lost 1 leaf, so each connected component contributes at least 1 leaf.

Therefore, for each connected component, it contributes either 1 leaf (for 1 vertex component) or at least 1 leaf (for > 1 vertex component). Therefore, with k components, we have at least k leaves .