Let
\(n=|V(G)|\text{.}\) If
\(T\) has only one vertex (and therefore no edges), then the result is trivial. So, assume that
\(T\) has at least two vertices. Let
\(r\) be an arbitrary root vertex of
\(T\) and define “parents” and “children” as in the proof of
Proposition 7.4.3.
Let \(T'\) be a graph obtained from \(T\) by adding \(|V(T)|-2\) isolated vertices. Note that
\begin{equation}
\hom(T',G) = n^{|V(T)|-2}\hom(T,G)\text{.}\tag{7.4.1}
\end{equation}
Consider a random homomorphism
\(f\) from
\(T'\) to
\(G\) where each of the vertices of
\(T\) are mapped according to the distribution described in
Proposition 7.4.3 and each isolated vertex is mapped to any given vertex
\(v\) of
\(G\) with probability
\(\frac{d(v)}{2|E(G)|}\) independently of all other vertices. Then, by
Lemma 7.1.4, we have
\begin{equation*}
\log(\hom(T',G))\geq \mathbb{H}(f)=\mathbb{H}(f(x): x\in V(T'))\text{.}
\end{equation*}
Label the vertices of \(T'\) by \(v_1,\dots,v_{2|V(T)|-2}\) in such a way that the first \(|V(T)|-1\) vertices are the isolated vertices and the root \(r\) of \(T\text{,}\) and if \(v_i\in V(T)\setminus \{r\}\text{,}\) then \(p(v_i)\) comes before \(v_i\) in the list. Then
\begin{equation*}
\mathbb{H}(f) = \mathbb{H}(f(v_1),\dots,f(v_{2|V(T)|-2}))=\sum_{i=1}^{2|V(T)|-2}\mathbb{H}(f(v_i)\mid f(v_1),\dots,f(v_{i-1}))\text{.}
\end{equation*}
Since the image of each vertex is conditionally independent of the image of all vertices that came before it, given its parent (if it has one), this can be rewritten as
\begin{equation*}
\sum_{i=1}^{|V(T)|-1}\mathbb{H}(f(v_i)) + \sum_{i=|V(T)|}^{2|V(T)|-2}\mathbb{H}(f(v_i)\mid f(p(v_i)))\text{.}
\end{equation*}
Let
\(V(K_2)=\{1,2\}\) and let
\(g\) be a uniformly random homomorphism from
\(K_2\) to
\(G\text{.}\) By
Claim 7.4.2 and
Proposition 7.4.3, we have that
\(f(v_i)\) has the same distribution as
\(g(1)\text{.}\) Also, for any
\(i\geq |V(T)|\text{,}\) the distribution of
\(f(v_i)\) given
\(f(p(v_i))\) is also identical to the distribution of
\(g(2)\) given
\(g(1)\text{.}\) If two random variables have the same distribution, then they have the same entropy. Thus, this expression can be rewritten as
\begin{equation*}
(|V(T)|-1)\mathbb{H}(g(1)) + (|V(T)|-1)\mathbb{H}(g(2)\mid g(1)) = |E(T)|\cdot \mathbb{H}(g(1),g(2))
\end{equation*}
\begin{equation*}
=|E(T)|\cdot \mathbb{H}(g)=|E(T)|\cdot\log(\hom(K_2,G))\text{.}
\end{equation*}
Therefore,
\begin{equation*}
\hom(T',G)\geq \hom(K_2,G)^{|E(G)|}\text{.}
\end{equation*}
Now, putting everything together, we get
\begin{equation*}
t(T,G)=\frac{\hom(T,G)}{n^{|V(T)|}} = \frac{\hom(T',G)}{n^{2|V(T)|-2}} \geq \frac{\hom(K_2,G)^{|E(T)|}}{n^{2|E(T)|}} = t(K_2,G)^{|E(T)|}
\end{equation*}
and so we are done.