Fix \(n \in \mathbb {N}\), and recall that a union-find state on \(n\) nodes is a function \(\mathrm{Fin}\, n \to \mathbb {N}\) assigning to each node a representative label. Every such state \(\mathit{uf}\) induces the same partition as itself: for all nodes \(i, j : \mathrm{Fin}\, n\), one has \(\mathit{uf}(i) = \mathit{uf}(j)\) if and only if \(\mathit{uf}(i) = \mathit{uf}(j)\).

Fix \(n \in \mathbb {N}\), and regard a union-find state on \(n\) nodes as a function \(\mathrm{Fin}\, n \to \mathbb {N}\) assigning each node a representative. If two such states \(\mathit{uf}_1\) and \(\mathit{uf}_2\) induce the same partition — that is, for all nodes \(i, j\) one has \(\mathit{uf}_1(i) = \mathit{uf}_1(j)\) if and only if \(\mathit{uf}_2(i) = \mathit{uf}_2(j)\) — then \(\mathit{uf}_2\) and \(\mathit{uf}_1\) likewise induce the same partition.

Let \(n\) be a natural number, and let \(\mathit{uf}_1, \mathit{uf}_2, \mathit{uf}_3 : \mathrm{Fin}\, n \to \mathbb {N}\) be three union-find states on \(n\) nodes. Suppose that \(\mathit{uf}_1\) and \(\mathit{uf}_2\) induce the same partition of the nodes, and that \(\mathit{uf}_2\) and \(\mathit{uf}_3\) induce the same partition. Then \(\mathit{uf}_1\) and \(\mathit{uf}_3\) induce the same partition: for all nodes \(i, j\), one has \(\mathit{uf}_1(i) = \mathit{uf}_1(j)\) if and only if \(\mathit{uf}_3(i) = \mathit{uf}_3(j)\).

Let \(\mathit{uf}\colon \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state on \(n\) nodes, and let \(i,j\) be two nodes whose representatives agree, \(\mathit{uf}(i) = \mathit{uf}(j)\). Then merging the components of \(i\) and \(j\) has no effect: the merged state equals \(\mathit{uf}\).

Let \(\mathit{uf} \colon \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state assigning each of \(n\) nodes a representative, and let \(\mathit{es}\) be a list of weighted edges over these \(n\) nodes. Suppose two nodes \(a, b \in \mathrm{Fin}\, n\) satisfy \(\mathit{uf}(a) = \mathit{uf}(b)\). Folding every edge of \(\mathit{es}\) into \(\mathit{uf}\) in sequence yields a union-find state \(\mathit{uf}'\) for which \(\mathit{uf}'(a) = \mathit{uf}'(b)\); that is, sequential merging never separates two nodes that already carry a common representative.

Fix \(n\) and let \(uf : \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state assigning each of the \(n\) nodes a representative. Let \(\mathit{base}\) and \(\mathit{edges}\) be lists of weighted edges on these \(n\) vertices, and suppose \(uf\) already encodes reachability along \(\mathit{base}\), in the sense that for all nodes \(a, b\) one has \(uf(a) = uf(b)\) if and only if \(a\) and \(b\) are connected by a path through the edges of \(\mathit{base}\). Then, writing \(uf'\) for the state obtained by merging the endpoints of every edge of \(\mathit{edges}\) into \(uf\) in order, for all nodes \(a, b\) one has \(uf'(a) = uf'(b)\) if and only if \(a\) and \(b\) are connected by a path through the edges of the concatenated list \(\mathit{base} \mathbin {+\! \! +} \mathit{edges}\).

Fix a natural number \(n\), and let \(\mathit{edges}\) be a list of weighted edges on the vertex set \(\mathrm{Fin}\, n\). Consider the union-find state obtained by starting from the initial state on \(n\) nodes, in which every node is its own representative, and processing \(\mathit{edges}\) in order, so that at each weighted edge the components of the two endpoints of that edge are merged. Then, for any two vertices \(a, b \in \mathrm{Fin}\, n\), the vertices \(a\) and \(b\) carry the same representative in the resulting state if and only if \(a\) and \(b\) are connected by a path through the edges of \(\mathit{edges}\) — equivalently, if and only if the reflexive–transitive closure of symmetric adjacency along \(\mathit{edges}\) relates \(a\) to \(b\).

Let \(\mathit{uf}_1, \mathit{uf}_2 : \mathrm{Fin}\, n \to \mathbb {N}\) be two union-find states over \(n\) nodes that induce the same partition, meaning that for all nodes \(i, j\) one has \(\mathit{uf}_1(i) = \mathit{uf}_1(j)\) if and only if \(\mathit{uf}_2(i) = \mathit{uf}_2(j)\). Then for any list of weighted edges, folding that list into each state by successively merging the endpoints of every edge yields two states that again induce the same partition.

Let \(n\) be a natural number, let \(\mathit{uf}\colon \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state, and let \(a\) and \(b\) be weighted edges over \(n\) vertices, with endpoints \(a_u, a_v\) and \(b_u, b_v\) respectively. Form one state by merging the components of \(a_u\) and \(a_v\) and then merging the components of \(b_u\) and \(b_v\), and a second state by performing these two merges in the opposite order. Then the two resulting states induce the same partition of the nodes: for all \(i, j : \mathrm{Fin}\, n\), the first state assigns \(i\) and \(j\) the same representative if and only if the second state does.

Fix \(n\) and an initial union-find state \(\mathit{uf} : \mathrm{Fin}\, n \to \mathbb {N}\). If two lists of weighted edges \(l_1\) and \(l_2\) over \(n\) vertices are permutations of one another, then folding each list into \(\mathit{uf}\) by merging the endpoints of every edge in turn yields two union-find states that induce the same partition of the nodes; that is, for all \(i, j : \mathrm{Fin}\, n\), the two states assign \(i\) and \(j\) equal representatives under one exactly when they do under the other.

Fix \(n \in \mathbb {N}\) and a union-find state \(\mathit{uf} \colon \mathrm{Fin}\, n \to \mathbb {N}\) on \(n\) nodes. For any list \(l\) of weighted edges over \(n\) vertices and any single weighted edge \(e\) over \(n\) vertices with endpoints \(u\) and \(v\), merging all edges of the list \(l \mathbin {+\! \! +} [e]\) into \(\mathit{uf}\) in order produces the same union-find state as first merging all edges of \(l\) into \(\mathit{uf}\) in order and then merging the components of \(u\) and \(v\) in the state so obtained.

Let \(\mathit{uf} : \mathrm{Fin}\, n \to \mathbb {N}\) be a union-find state on \(n\) nodes, let \(e\) be a weighted edge with endpoints \(u\) and \(v\) over these nodes, and let \(S\) be a list of weighted edges over the same nodes. Folding the list \(e :: S\) into \(\mathit{uf}\) and folding the list \(S\) into the union-find state that merges the components of \(u\) and \(v\) in \(\mathit{uf}\) induce the same partition of the nodes: for all nodes \(i\) and \(j\), folding \(e :: S\) into \(\mathit{uf}\) assigns \(i\) and \(j\) a common representative if and only if folding \(S\) into the merge of \(u\) and \(v\) assigns \(i\) and \(j\) a common representative.

Let \(l\) be a finite list of weighted edges over \(n\) vertices, and let \(e\) be a weighted edge that occurs in \(l\). Then \(l\) is a permutation of the list obtained by deleting the first occurrence of \(e\) from \(l\) and appending \(e\) at the end.