Assume that you have a finite tree $T=(V,E)$, where $V$ and $E$ are the set of vertices and edges of $T$, respectively. Let $d_{max}$ be the maximum degree the some vertice(s) $v\in{V}$. Assume also that you have and infinite $d$-regular tree $T'=(V',E')$ with $d\geq{d_{max}}$.
How can I define a map from $V\rightarrow{V'}$ such that for every $u,v\in{V}$ there exist a vertex $t$ adjacent to $u$ with $d(f(t),f(v))<{d(f(u),f(v))}$?
I know that this map exists by intuition, however I don't know how to describe it mathematically (p.s. I'm from computer sciences).
thanks.
You can view both $T$ and $T'$ as rooted trees by designating a vertex as the root arbitrarily. Define $r$ and $r'$ as the respective roots of $T$ and $T'$. We now work with these rooted viewings, which define an ancestor/descendant relationship between the vertices. For some $v \in V \cup V'$, choose an ordering of the children of $v$ and denote the $i$-th child of $v$ as $Ch_i(v)$.
You can define $f$ as $f(r) = r'$, and recursively for some $v \in V$, let $f(Ch_i(v)) = Ch_i(f(v))$ for all children of $v$ (noting that $Ch_i(f(v))$ must exist since $f(v)$ has at least as many children as $v$). Essentially $f$ finds a subtree of $T'$ that is isomorphic to $T$.
Now, for some $u, v \in V$. If $v$ is an ancestor of $u$ (ie $v$ is on the path from $u$ to $r$ in the rooted view of $T$), take $t$ as the parent of $u$, and $d(f(t), f(v)) < d(f(u), f(v))$ is immediate.
If $v$ is a descendent of $u$, take $t$ as the single child of $u$ on the path from $u$ to $v$ in $T$. The same argument applies.
So the last case is when $u$ and $v$ are 'unrelated', meaning that none is an ancestor of the other. This means the $u,v$ path goes through the parent of $u$. So take $t$ as the parent of $u$, and the rest follows.