Given a set of trees with leaves labelled from a set L, is there a tree T with leaves labelled by L such that each of the given trees is homeomorphic to a subtree of T? This question is known to be NPcomplete in general, but solvable in polynomial time if all the given trees have one label in common ( equivalently, if the given trees are rooted). Here we show that this problem is NP-complete even if there are two labels x and y such that each given tree contains x or y. On the other hand, we show that the question of whether a fully resolved (binary) tree exists which has no subtree homeomorphic to one of the given ones is NP-complete, even when the given trees are rooted. This sheds some light on the complexity of determining whether a probability assignment to trees is coherent.