and are two trees without having a vertex of degree . Each edge of them has a positive number named the length of the edge. The distance between two vertices is the sum of the length of the edges of the path between them. We call the vertices with degree , leaf. is an injective and surjective function from the set of leaves of to the set of leaves of with this property that for every two leaves and in , the distance between and in is equal to the distance between and in . Prove that there exists an injective and surjective function from the set of vertices of to the set of vertices of such that for every two vertices and in , the distance between and in , is equal to the distance between and in .
Solution
It is obvious that the total number of the leaves of and are equal. We solve the problem using induction. The base case for leaves is trivial because there is no vertex of degree . Now suppose that have leaves. Let
in which is a leaf. It means that we omitted leaf from , and leaf from . Assume the induction hypothesis holds for , so there is a correspondence between their vertices, like . Now let be the neighbor of in , and be the neighbor of in . It is enough that we prove that and the length of the edge is equal to the length of the edge .
First note that if be two leaves in and the path between , intersects the path between for the first time in vertex , then we have: (let denote the length of the path between and )
And since doesn't have a -degree vertex:
Now do the same for . Thus, because these two values for a pair and its correspondence , minimizes, so and the length of the edge is equal to the length of the edge , hence the induction and proof are complete.