A parent-map bound for isolated components

Fix a $k$-vertex set $S$ and root it at its least labelled vertex. If the induced graph on $S$ is connected, every other vertex has a shortest path to the root. Choose as its parent the least labelled neighbor whose distance to the root is one smaller. Following parents strictly decreases distance and reaches the root, so the resulting $k-1$ distinct edges form a connected spanning graph with no cycle. There are at most $k^{k-1}$ parent maps, since each nonroot vertex chooses an element of $S$. Each map arising this way requires $k-1$ distinct internal edges.

For $S$ to be a component, its $k(n-k)$ crossing pairs must be absent. For each valid parent map from step 1.1 its internal required edges and those crossing pairs are disjoint. Independence gives probability $p^{k-1}(1-p{)}^{k(n-k)}$ for these requirements. Sum over at most $k^{k-1}$ maps and then over the $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ sets $S$. The indicator of a union is bounded by the sum of its indicators; applying the finite expectation formula proves the bound, also at $p=0,1$ with zero exponents interpreted as empty products.