Bounding the number of distance-3-sets in an undirected graph Let $G = (V,E)$ be an undirected $n$-vertex graph with maximum degree $\Delta$ and let $T \subset$ V be a distance-3-set such that:
1) The distance between all vertices $v \in T$ is at least 3 
2) The size of the set is $|T|=t$ 
3) $T$ forms a tree in $G^3$, where $G^3 = \{V(G), (u,v) | dist_G(u,v) = 3\}$, that is, there are edges between all vertices that have a shortest distance of 3.

Claim: There are less than $4^t \cdot n \cdot \Delta^{3(t-1)}$ distance-3 sets.

How do you see that is in fact the case? I seems like the intuition is linked to each outgoing edge of each vertex but I don't understand how..
 A: So... I didn't get to that final result, yet, but here are my thoughts so far - perhaps someone can extend them or find the path I didn't take.

We know that the maximum degree of $G^3$ is no more than $\Delta^3$. In the following I'll ignore the reduction in choice due to previous choices. The option count looks to me like:

*

*choose an initial vertex ($n$)

*add $t-1$ edges, choosing from no more than $\Delta^3$, $2\cdot\Delta^3$, $3\cdot\Delta^3$, $\ldots$, $(t{-}1)\cdot\Delta^3$ options successively,

giving $(t{-}1)!\cdot n\cdot \Delta^{3(t{-}1)}$ options - when the order of construction is labelled onto the vertices. However we're not interested in the order of construction of the tree, so we can divide out the number of different ways that trees can be given a construction-order type labelling.
The tree with the least number of such labellings is a path. Every branch (of $3{+}$ degree) gives an increase in ways to construct/label the tree.
So dividing through by the smallest possible number of construction labellings. A path of $t$ nodes can be so labelled by choosing the first node and then choosing on which steps to build to the left (building right on other steps). This is the sum of all possible ways of choosing $k$ from $t{-}1$ across all $k$, which is $2^{t{-}1}$ from the combinatoric identity.
Unfortunately this doesn't quite get us where we are aiming for; this shows the number of trees is less than  $$\frac{(t{-}1)!}{2^{t{-}1}}\cdot n\cdot \Delta^{3(t{-}1)}$$ but that first term can still exceed the $4^t$ we want.
