Prove that every tree with maximum degree x has at least x leaves.
Any thoughts? Thanks.
Follow Math Help Forum on Facebook and Google+
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.
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
View Tag Cloud