# Spanning tree in a graph of intersecting sets

Consider $$n$$ sets, $$X_i$$, each having $$n$$ elements or fewer, drawn among a set of at most $$m \gt n$$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\right| \le m$$

Consider the complete graph $$G$$ formed by taking every $$X_i$$ as a node, and weighing every edge $$(i,j)$$ by the cardinal of the symmetric difference $$X_i \triangle X_j$$.

An immediate bound on the weight of the minimal spanning tree is $$\mathcal{O}(n^2)$$, since each edge is at most $$2 n$$, but can we refine this to $$\mathcal{O}(m)$$?

For illustration, consider $$2 p$$ sets, $$p$$ of which contain the integers between $$1$$ and $$p$$ and $$p$$ of which contain the integers of between $$p+1$$ and $$2p$$. A minimal spanning tree has weight $$p$$ but a poorly chose tree on this graph would have weight $$(p-1)p$$. Intuitively, if there are only $$m$$ values to chose from, the sets can’t all be that different from one another.