  We prove a surprising symmetry between the law of the size $G_n$ of the
greedy independent set on a uniform Cayley tree $ \mathcal{T}_n$ of size $n$
and that of its complement. We show that $G_n$ has the same law as the number
of vertices at even height in $ \mathcal{T}_n$ rooted at a uniform vertex. This
enables us to compute the exact law of the $G_n$. We also give a Markovian
construction of the greedy independent set, which highlights the symmetry of
$G_n$ and whose proof uses a new Markovian exploration of rooted Cayley trees
which is of independent interest.
