# Thread: Graph Theory Problem #2

1. ## Graph Theory Problem #2

Prove that every tree with maximum degree x has at least x leaves.

Any thoughts? Thanks.

2. For each edge incident to a vertex with maximum degree, proceed along any path starting with that vertex and edge. The path has to end somewhere without looping back, as the graph is acyclic. Thus we have a leaf for each such path.

3. Originally Posted by jzellt
Prove that every tree with maximum degree x has at least x leaves.

Any thoughts? Thanks.
Let v be vertex of degree x . Every maximal paths starts from v will end with leaf. No two such path intersects since tree has no cycle . Therefore tree has atleast x leaves