Let \(\mathit{base}\) and \(\mathit{rest}\) be lists of weighted edges on \(n\) vertices, and let \(g\) and \(e\) be two further weighted edges, with respective endpoints \(u_g, v_g\) and \(u_e, v_e\). Suppose that, using only the edges in the concatenation \(\mathit{base} \mathbin {+\! \! +} \mathit{rest}\), the vertex \(u_e\) is connected to \(u_g\) and the vertex \(v_g\) is connected to \(v_e\). Then for every pair of vertices \(a, b\) that are connected using the edges of \(\mathit{base} \mathbin {+\! \! +} (g :: \mathit{rest})\), the vertices \(a\) and \(b\) are also connected using the edges of \(\mathit{base} \mathbin {+\! \! +} \mathit{rest} \mathbin {+\! \! +} [e]\).

Fix \(n\) and consider weighted edges on a vertex set of size \(n\), each edge carrying a first and a second endpoint. For a list of edges \(L\), write \(a \leadsto _L b\) to mean that \(a\) reaches \(b\) through \(L\), i.e. \(a\) and \(b\) are joined by a path whose edges lie in \(L\) (the reflexive–transitive closure of the symmetric adjacency relation induced by \(L\)). Let \(\mathit{base}\) and \(\mathit{rest}\) be lists of weighted edges, and let \(g\) and \(e\) be weighted edges, with first and second endpoints \(g_1, g_2\) and \(e_1, e_2\) respectively. Suppose that, using the edges in the concatenation \(\mathit{base} \mathbin {+\! \! +} \mathit{rest}\), the endpoint \(e_1\) reaches \(g_2\) and the endpoint \(g_1\) reaches \(e_2\). Then for every pair of vertices \(a, b\): if \(a \leadsto b\) using the list obtained by placing \(g\) at the front of \(\mathit{rest}\) and appending that to \(\mathit{base}\), then \(a \leadsto b\) using \(\mathit{base} \mathbin {+\! \! +} \mathit{rest} \mathbin {+\! \! +} [e]\), the concatenation of \(\mathit{base}\), \(\mathit{rest}\), and the single edge \(e\).

Let \(\mathit{base}\) and \(S\) be lists of weighted edges on \(n\) vertices, and let \(e\) be a weighted edge whose two endpoints are distinct. Suppose the endpoints of \(e\) are connected by a path using the edges of \(\mathit{base}\) together with those of \(S\), but are not connected using the edges of \(\mathit{base}\) alone. Then there is an edge \(f\) occurring in \(S\) such that, for every pair of vertices \(a\) and \(b\) connected by a path through the edges of \(\mathit{base}\) together with \(S\), the vertices \(a\) and \(b\) are still connected by a path through the edges of \(\mathit{base}\) together with the edges of \(S\) after removing one occurrence of \(f\) and adjoining \(e\).

Let \(\mathit{uf}\colon \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state whose classes coincide with the reachability classes of an edge list \(\mathit{base}\): for all nodes \(a,b\) one has \(\mathit{uf}(a) = \mathit{uf}(b)\) if and only if \(a\) and \(b\) are joined by a path through the edges of \(\mathit{base}\). Let \(S\) be a further list of weighted edges, and let \(e\) be a weighted edge with endpoints \(u\) and \(v\) such that merging every edge of \(S\) into \(\mathit{uf}\) places \(u\) and \(v\) in a common component, while \(\mathit{uf}\) itself keeps them in distinct components. Then there is an edge \(f \in S\) for which the state obtained by first merging \(u\) with \(v\) and then merging all edges of \(S\) other than \(f\) induces the same partition of the nodes as the state obtained by merging all edges of \(S\) into \(\mathit{uf}\).

Let \(\mathit{uf}\) be a union-find state on \(n\) nodes, let \(e\) be a weighted edge with endpoints \(u\) and \(v\), and let \(\mathit{rest}\) and \(S\) be lists of weighted edges. Suppose every edge of \(S\) occurs in the list \(e :: \mathit{rest}\) formed by prepending \(e\) to \(\mathit{rest}\); that merging all edges of \(S\) into \(\mathit{uf}\) induces the same partition of the nodes as merging all edges of \(\mathit{rest}\) into \(\mathit{uf}\); and that \(e\) is already redundant for \(\mathit{uf}\), meaning \(\mathit{uf}(u) = \mathit{uf}(v)\). Then there exists a list \(S'\) of weighted edges, every one of which occurs in \(\mathit{rest}\), such that merging all edges of \(S'\) into \(\mathit{uf}\) induces the same partition as merging all edges of \(\mathit{rest}\), and the total weight of \(S'\) is at most the total weight of \(S\).