${{\mathcal S}}$. Let $S$ be the ST-set of largest cardinality that contains $x$; such an ST-set must exist because $\{ x \}$ is an ST-set. $S \not \in {{\mathcal S}}$ so there exists some ST-set $S'$ such that $S \subset S'$, but this contradicts the assumption on the cardinality of $S$. Hence ${{\mathcal S}}$ partitions ${{\mathcal X}}$, and by extension ${{\mathcal S}}$ is unique.

\[lem:polymax\] The maximal ST-sets of a set of clusters ${{\mathcal C}}$ on ${{\mathcal X}}$ can be computed in polynomial time.

Deferred to the appendix.

Corollary \[cor:mostn\] and Lemma \[lem:polymax\] are perhaps not so surprising, but we have nevertheless proven them rigorously to highlight the fact that *computing* maximal ST-sets is not a complexity bottleneck. In later sections we shall see that there is a link between NP-hardness and maximal ST-sets, but that the hardness lies in selecting certain maximal ST-sets with special properties, not in the computation of the maximal ST-sets *per se*.

Let $\mathcal{T}$ be a set of trees, where each $T \in \mathcal{T}$ is a tree on $\mathcal{X}$. For a tree $T$ we write $Cl(T)$ to denote the set of clusters induced by edges of $T$ i.e. $C \in Cl(T)$ if and only if 