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

- Sep 22nd 2010, 07:22 PMjzelltTree Proof
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! - Sep 22nd 2010, 07:36 PMundefined
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.

Illustration for x = 4.