e$.

In the remainder of the proof, we illustrate a simple algorithm for determining whether a binary simple level-$k$ network that represents ${{\mathcal C}}$ exists by attempting to reconstruct such a network. Let $g$ be the generator underlying $N$. We only require polynomially many tries to compute $g$, because there are only a constant number of generators. So assume we know $g$. For each side of $g$, we guess whether there are 0, 1, 2 or more than 2 leaves on that side. For each side containing exactly one leaf, we guess what that is. For each side $s$ of $g$ containing 2 or more leaves, we guess the leaf $s^{+}$ that is nearest to the root on that side, and the leaf $s^{-}$ that is furthest from the root on that side. For an example see Figure \[fig:exLemma1\]. Note that, since for each side we have only four options (0, 1, 2 or more than 2 leaves), and in the latter case only $s^{+}$ and $s^{-}$ have to be chosen, if follows that we have a polynomial number of guesses to try.

We will now show how to add the remaining leaves. Note that we may fail to insert 