Show that for every choice of n and x with n > x > 1 there is a tree on n vertices
with maximum degree x that has exactly x leaves.
Any advice? I'm at a loss... Thanks!
Printable View
Show that for every choice of n and x with n > x > 1 there is a tree on n vertices
with maximum degree x that has exactly x leaves.
Any advice? I'm at a loss... Thanks!
The question itself, based on a few drawings on paper I think for (n,x) = (n,n-1) you can use the graph that has a single root connected to all leaves, and then for getting (n+1,n-1), just take one of the branches and put an intermediate vertex which will have degree two, which process can be continued indefinitely.Quote:
Originally Posted by jzellt
Illustration for x = 4.