Let f : [n] → [n] be a function, and let Tf be a labelled tree on n vertices, constructed from f. Suppose that T contains a vertex of degree at least k. Show that f takes at most n-k+2 different values.
I don't really know how to start here.
Thanks.
Asked
Active
Viewed 164 times
1
-
A usual way to define a tree from $f\colon [n] \to [n]$ is to take $f$ to be the function that gives the parent of a node. One node of the tree is the root and has no parent. Is this your setup? – Fabio Somenzi Apr 02 '17 at 01:44
-
@FabioSomenzi I know the following, and that's kind of how we defined it : The map f → T associates to every function f as above, a labelled tree T on n vertices with 2 vertices marked as red and blue. The number i belonging to [n] can be a leaf of T if and only if i is not a value of f, or either red or blue vertices. Do you see the setup ? – TedMosby Apr 02 '17 at 01:54
-
I'm afraid I don't. What are these two special vertices doing? Could you add an example to your post? – Fabio Somenzi Apr 02 '17 at 02:03