Across two different texts, I have seen two different definitions of a leaf
1) a leaf is a node in a tree with degree 1
2) a leaf is a node in a tree with no children
The problem that I see with def #2 is that if the graph is not rooted, it might not be clear whether a node, n, has adjacent nodes that are its children or its parents
So is it just always safer to go with def #1? Or is def #2 restricted to rooted trees? Why do some authors present these definition differently?
$\endgroup$ 11 Answer
$\begingroup$Let's look at an unrooted tree with two nodes $v_{1}, v_{2}$. Either could be the root, but both are leaves.
Now consider $P_{2}$, a path of length $2$, which has $3$ vertices. Only the middle vertex is not a leaf. If one of the endpoints was selected as the root, it would have exactly child. If the middle vertex was selected, it would be a root that was not a leaf.
While there is a bit of ambiguity with definition (2), I would go with definition (1). It has the most power and least ambiguity. I really don't like definition (2) either.
I hope this clarifies some.
$\endgroup$
