Let \(G\) be a multigraph on a vertex type \(\alpha \), and suppose \(e\) is an edge of \(G\). Then the edge count of \(G\), the number of edges counted with multiplicity, is strictly positive.

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut of that multigraph. If \(t\) arises from \(s\) by a surviving step — that is, \(t\) is obtained by contracting some edge \(e\) of the multigraph of \(s\) that does not cross the distinguished cut of \(s\) — then the two distinguished cuts have the same size; equivalently, the number of edges crossing the distinguished cut of \(t\), counted with multiplicity, equals the number of edges crossing the distinguished cut of \(s\).

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\) of \(G\), and let \(t\) be a state obtained from \(s\) by a surviving step: that is, \(t\) arises by contracting some edge \(e\) of \(G\) that does not cross \(C\), so that \(t\) has graph \(G/e\) and its distinguished cut is the cut induced by \(C\) on \(G/e\). If \(C\) is a minimum cut of \(G\), then the distinguished cut of \(t\) is a minimum cut of \(G/e\).

Let \(s\) and \(t\) be states of the contraction process, each a multigraph together with a distinguished cut, and suppose that \(t\) arises from \(s\) by a surviving step, that is, \(t\) is obtained by contracting some edge \(e\) of the multigraph of \(s\) that does not cross the distinguished cut of \(s\). Then the number of vertices of the multigraph of \(t\) equals the number of vertices of the multigraph of \(s\) minus \(1\) (with the difference taken in \(\mathbb {N}\)).

Let \(s\) and \(t\) be states of the contraction process, each a multigraph equipped with a distinguished cut. If \(t\) arises from \(s\) by a surviving step — that is, by contracting some edge of the multigraph of \(s\) that does not cross the distinguished cut of \(s\) — then the multigraph of \(s\) has positive edge count.

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut, and suppose that \(t\) is obtained from \(s\) by a surviving run of length \(n\), that is, by \(n\) consecutive contractions of edges that do not cross the distinguished cut of the current state. Then the distinguished cut of \(t\) has the same size as the distinguished cut of \(s\), where the size of a cut is the number of its crossing edges counted with multiplicity.

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut of that multigraph, and suppose that \(t\) is obtained from \(s\) by a surviving run of some length \(n\), that is, by \(n\) consecutive contractions of edges that never cross the distinguished cut. If the distinguished cut of \(s\) is a minimum cut of its multigraph, then the distinguished cut of \(t\) is a minimum cut of its multigraph.

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut, and suppose that \(t\) is reached from \(s\) by a surviving run of length \(n\), that is, by \(n\) consecutive contractions of edges that do not cross the tracked cut. Writing \(G_s\) and \(G_t\) for the multigraphs of \(s\) and \(t\), and \(\lvert V(G)\rvert \) for the number of vertices of a multigraph \(G\), we have

where the subtraction is truncated subtraction on \(\mathbb {N}\) (equal to \(0\) once \(n\) exceeds \(\lvert V(G_s)\rvert \)).

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut, and suppose that \(t\) is obtained from \(s\) by a surviving run of some length \(n\), that is, by \(n\) successive contractions of edges that do not cross the distinguished cut. If the distinguished cut \(C\) of \(s\) is a minimum cut of the multigraph \(s.G\), with size \(k\) (its number of crossing edges), then the number of vertices \(|V|\) and the number of edges \(|E|\) of the final multigraph \(t.G\) satisfy

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut, and suppose \(t\) is reached from \(s\) by a surviving run of \(n\) steps. Write \(C\) for the distinguished cut of \(s\) and \(G\) for its multigraph, and let \(G'\) denote the multigraph of \(t\). If \(C\) is a minimum cut of \(G\), then

where \(\left\lvert C\right\rvert \) is the size of the cut (its number of crossing edges), \(\left\lvert V(G)\right\rvert \) is the number of vertices of \(G\), \(\left\lvert E(G')\right\rvert \) is the number of edges of \(G'\) counted with multiplicity, and the difference \(\left\lvert V(G)\right\rvert - n\) is truncated at \(0\).

Let \(c\), \(n\), and \(m\) be natural numbers with \(n \ge 2\), \(m \gt 0\), and \(cn \le 2m\). Then the one-step survival probability \(1 - \frac{c}{m}\) satisfies

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\) of \(G\). Suppose that a surviving step is possible from \(s\), meaning that \(G\) has an edge that does not cross \(C\), whose contraction — merging the endpoints of that edge, deleting the resulting self-loops, and passing to the cut that \(C\) induces on the contracted graph — yields a further state of the process. Assume moreover that \(C\) is a minimum cut of \(G\) and that \(G\) has at least two vertices. Writing \(n\) for the number of vertices of \(G\), \(k\) for the size of \(C\) (its number of crossing edges, counted with multiplicity), and \(m\) for the number of edges of \(G\) (counted with multiplicity), one has

so that \(\frac{n-2}{n}\) is at most the one-step survival probability of \(C\).

Let \(s\), \(t\), and \(u\) be states of the contraction process, each a multigraph paired with a distinguished cut. Suppose \(t\) is reached from \(s\) by a surviving run of \(i\) steps, that a further surviving step leads from \(t\) to \(u\), that the distinguished cut of \(s\) is a minimum cut of the multigraph of \(s\), and that the multigraph of \(t\) has at least two vertices. Writing \(n_t\) for the number of vertices of the multigraph of \(t\), \(c\) for the size of the distinguished cut of \(s\), and \(m\) for the number of edges of the multigraph of \(t\), then

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\), whose two sides are given by a vertex subset \(S\) and its complement. Then the number of edges of \(G\) that do not cross \(C\) — those having no endpoint in \(S\) or no endpoint outside \(S\), counted with multiplicity — equals the total edge count of \(G\) minus the size of \(C\), the difference being taken as truncated subtraction in \(\mathbb {N}\):

Let \(G\) be a multigraph and let \(C\) be a cut of \(G\), given by a vertex subset \(S\) that is nonempty and has nonempty complement. Then the size of \(C\) — the number of edges of \(G\) having exactly one endpoint in \(S\), counted with multiplicity — is at most the total number of edges of \(G\), again counted with multiplicity.

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\), and suppose \(G\) has at least one edge, so that its edge count \(m\) is positive. Then the uniform one-step survival probability of \(s\) — the number of non-crossing edge choices divided by \(m\) — equals

where \(c\) is the size of the cut \(C\), that is, its number of crossing edges (each counted with multiplicity).

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a cut of \(G\), and let its sample space of edge occurrences be the finite set of pairs (edge, occurrence index) drawn from the edge multiset of \(G\). Then this sample space has cardinality equal to the edge count of \(G\), that is, the number of edges of \(G\) counted with multiplicity.

Let \(\alpha \) be a type with decidable equality, let \(m\) be a finite multiset over \(\alpha \), and let \(p\) be a decidable predicate on \(\alpha \). Form the enumeration set of \(m\), consisting of all pairs \((a, i)\) with \(a\) an element of \(m\) and \(0 \le i \lt \text{count}_m(a)\), so that each occurrence of each element of \(m\) is represented exactly once. Then the number of such pairs \((a,i)\) whose first coordinate \(a\) satisfies \(p\) equals the size (counted with multiplicity) of the sub-multiset of \(m\) consisting of the elements satisfying \(p\).

Let \(s\) be a state of the contraction process, consisting of a loopless multigraph \(G\) together with a distinguished cut \(S \subseteq V(G)\), and enumerate the edge multiset of \(G\) as a finite set of edge occurrences \((e, i)\), where the index \(i\) distinguishes parallel copies of the same edge. Say that an occurrence \((e, i)\) survives when its underlying edge \(e\) does not cross \(S\), that is, when it is not the case that one endpoint of \(e\) lies in \(S\) and the other lies outside \(S\). Then the number of surviving edge occurrences equals the number of edges of \(G\) that do not cross \(S\), counted with multiplicity.

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\) of \(G\). Form the survival ratio by enumerating the edge occurrences of \(G\) — the pairs of an edge with an index distinguishing its parallel copies — and dividing the number of occurrences whose underlying edge does not cross \(C\) by the total number of occurrences. Then this ratio equals the uniform survival probability of \(s\), namely the number of edges of \(G\) that do not cross \(C\), counted with multiplicity, divided by the total edge count of \(G\).

Let \(s\) be a state of the contraction process, with underlying multigraph \(G\), and let \((e, k)\) be any element of the sample space of edge occurrences of \(s\) — a pair consisting of an edge together with an index distinguishing parallel copies. Then the edge \(e\) is a member of the edge multiset of \(G\).

Let \(s = (G, C)\) be a state of the contraction process, consisting of a multigraph \(G\) and a distinguished cut \(C\) with side \(S\), and let \((e, i)\) be an edge occurrence in the sample space of \(s\), so that \(e\) is an edge of \(G\) and \(i\) indexes its parallel copies. If this occurrence survives — that is, if \(e\) does not cross \(S\), meaning it is not the case that \(e\) has one endpoint in \(S\) and another endpoint outside \(S\) — then \(e\) does not belong to the multiset of crossing edges of \(C\).

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(C\) of \(G\), and let a sampled edge occurrence be given in the sample space of \(s\) — a pair (edge, occurrence index) drawn from the edge multiset of \(G\) — whose underlying edge does not cross \(C\). Then the pair formed by \(s\) and the successor state obtained by contracting \(s\) along that edge occurrence stands in the surviving-step relation; that is, the successor state arises from \(s\) by contracting some edge of \(G\) that does not cross \(C\).

For every state \(s\) — a multigraph \(G\) together with a distinguished cut \(C\) of \(G\) — the recursive survival probability of the distinguished cut over zero random edge-occurrence choices equals \(1\).

Let \(s\) be a state, consisting of a multigraph \(G\) together with a distinguished cut \(C\) of \(G\), and let \(\mathrm{steps}\) be a natural number. Write \(P_k(s)\) for the survival probability of the cut over \(k\) random edge-occurrence choices starting from \(s\). Then

where the sum ranges over the finite set of edge occurrences of \(G\) (each parallel copy of an edge counted separately), \(N\) is the number of such occurrences, and \(s_c\) denotes the state obtained by contracting \(s\) along the underlying edge of a surviving occurrence \(c\).

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut \(S\) of \(G\), and let \(\Omega \) be its sample space of edge occurrences — the finite set of pairs \((e, i)\) where \(e\) is an edge of \(G\) and \(i\) is an occurrence index distinguishing parallel copies of that edge. Call an occurrence *surviving* when its underlying edge \(e\) does not cross \(S\), that is, when it is not the case that one endpoint of \(e\) lies in \(S\) and the other lies outside \(S\). Then the number of surviving occurrences is the same whether they are counted directly among the elements of \(\Omega \) or among the elements of the equinumerous copy of \(\Omega \) obtained by regarding each member together with the fact that it belongs to \(\Omega \); in both counts the survival test is applied to the underlying occurrence, and the two cardinalities agree.

Let \(S\) be a finite set, let \(p\) be a predicate on \(S\), and let \(f\colon S \to \mathbb {R}\). Suppose \(B \in \mathbb {R}\) is a lower bound for \(f\) on the elements satisfying \(p\), that is, \(B \le f(x)\) for every \(x \in S\) with \(p(x)\). Then

Let \(s\) be a state of the contraction process — a multigraph together with a distinguished cut — and assume that its sample space of edge occurrences is nonempty. Fix a natural number \(k\) and a real number \(B\), and suppose that for every edge occurrence that survives, meaning its underlying edge does not cross the distinguished cut, the recursive survival probability over \(k\) further choices, evaluated at the successor state obtained by contracting \(s\) along that occurrence, is at least \(B\). Then the recursive survival probability over \(k+1\) choices at \(s\) is at least the survival ratio of \(s\) multiplied by \(B\).

Let \(s\) be a state of the contraction process — a multigraph \(G\) together with a distinguished cut \(C\) of \(G\) — and write \(n\) for the number of vertices of \(G\). Suppose that \(C\) is a minimum cut of \(G\), that the size of \(C\) is strictly positive, and that \(n \ge 2\). Then the survival ratio of the edge-occurrence sample space of \(s\) is at least \(\tfrac {n-2}{n}\); that is,

where \(\rho (s)\) is the fraction of edge occurrences whose underlying edge does not cross \(C\).

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut of \(G\). Then the graph-only occurrence space built from \(G\) coincides, as a finite set of edge occurrences \((e, k) \in \mathrm{Sym}_2\, \alpha \times \mathbb {N}\), with the state’s sample space of edge occurrences; that is, both are the set of edge occurrences of the state’s underlying multigraph.

Let \(G\) be a multigraph, and let its graph-only occurrence space be the finite set of edge occurrences of \(G\), whose elements are pairs \((e, k)\) consisting of an edge \(e\) together with an index \(k\) distinguishing the copies of \(e\) among the parallel edges of \(G\). Then for every occurrence \((e, k)\) in this space, the edge \(e\) belongs to the edge multiset of \(G\).

Let \(G\) be a multigraph on a vertex type \(\alpha \) with decidable equality, and let \(c\) be a sampled edge occurrence of \(G\), i.e. an element of its finite set of edge occurrences. Writing \(G_c\) for the multigraph obtained by contracting \(G\) along the edge underlying \(c\), the number of vertices of \(G_c\) equals the number of vertices of \(G\) minus one.

Let \(s\) be a state of the contraction process, comprising a multigraph \(G\) together with a distinguished cut \(C\), and let \((e, i)\) be an edge occurrence of \(G\) drawn from its sample space of edge occurrences, whose underlying edge \(e\) does not cross \(C\). Then the multigraph carried by the successor state obtained by contracting \(s\) along this occurrence is equal to the multigraph obtained by contracting \(G\) itself along the same occurrence, namely the contraction \(G/e\).

Let \(G\) and \(H\) be multigraphs on a vertex type \(\alpha \), and let \(\mathrm{steps} \in \mathbb {N}\). If \(H\) arises from \(G\) by a graph-only Karger run consisting of \(\mathrm{steps}\) successive edge-occurrence contractions, then the number of vertices of \(H\) equals the number of vertices of \(G\) minus \(\mathrm{steps}\), using truncated subtraction of natural numbers. Thus each contraction removes exactly one vertex, and after \(\mathrm{steps}\) of them the vertex count has dropped by \(\mathrm{steps}\).

Let \(G\) and \(H\) be multigraphs on a common vertex type, and suppose \(G\) has at least two vertices. If \(H\) is obtained from \(G\) by a graph-only Karger run consisting of exactly \(n - 2\) successive edge-occurrence contractions, where \(n\) is the number of vertices of \(G\), then \(H\) has exactly two vertices.

Let \(G\) be a multigraph with at least two vertices, write \(n\) for its vertex count, and suppose \(H\) is obtained from \(G\) by a graph-only Karger run consisting of exactly \(n - 2\) successive edge-occurrence contractions. Then \(H\) satisfies the termination condition of the algorithm; that is, \(H\) has exactly two vertices.

Let \(G\) be a multigraph on a vertex type \(\alpha \), and let \(e\) be an edge of \(G\), that is, a member of the edge multiset of \(G\). Then the occurrence \((e, 0)\) belongs to the graph-only occurrence space of \(G\); in other words, the pair consisting of \(e\) together with the index \(0\) is one of the enumerated edge occurrences of \(G\).

Let \(s\) and \(t\) be states of the contraction process, each consisting of a multigraph together with a distinguished cut of it. If \(t\) arises from \(s\) by a surviving step—that is, by contracting some edge of \(s\)’s multigraph that does not cross its distinguished cut—then there is an edge occurrence in the graph-only occurrence space of \(s\)’s multigraph whose sampled contraction produces exactly the multigraph of \(t\).

Let \(s\) and \(t\) be states of the contraction process over a vertex type \(\alpha \), each consisting of a multigraph together with a distinguished cut of it. If \(t\) is reached from \(s\) by a surviving run of some number \(\mathrm{steps}\) of consecutive surviving steps — each contracting an edge that does not cross the current distinguished cut — then the underlying multigraph of \(t\) is reached from the underlying multigraph of \(s\) by a graph-only Karger run of the same length \(\mathrm{steps}\), that is, by \(\mathrm{steps}\) successive edge-occurrence contractions.

Let \(s\) be a state of the contraction process, consisting of a multigraph \(G\) together with a distinguished cut of \(G\), and write \(n\) for the number of vertices of \(G\); suppose \(n \ge 2\). If a state \(t\) is reached from \(s\) by a surviving run of exactly \(n - 2\) consecutive surviving steps — each step contracting an edge of the current graph that does not cross the distinguished cut — then the multigraph of \(t\) satisfies the termination condition of the algorithm, that is, it has exactly two vertices.

Let \(T\) be an adaptive graph trace of length \(\text{steps}\), so that \(T\) records a graph at each index, a sampled edge occurrence at each index below \(\text{steps}\), and produces each successive graph as the contraction of its predecessor along that occurrence. Then for every index \(i \le \text{steps}\), the graph-only Karger run relation holds for \(i\) steps between the initial graph \(T_0\) and the graph \(T_i\); that is, \(T_i\) is reachable from \(T_0\) by exactly \(i\) successive edge-occurrence contractions.

Let \((G_i)_{i \in \mathbb {N}}\) be an adaptive contraction trace over \(\text{steps}\) rounds on a vertex type with decidable equality: a family of multigraphs in which, for each index \(i \lt \text{steps}\), the graph \(G_{i+1}\) is obtained from \(G_i\) by contracting the edge underlying a sampled edge occurrence of \(G_i\). Then for every \(i \le \text{steps}\), the number of vertices of \(G_i\) equals the initial vertex count minus \(i\); that is, \(\lvert V(G_i)\rvert = \lvert V(G_0)\rvert - i\).

Let \(n \ge 2\), and let \(T\) be an adaptive graph trace of \(n-2\) steps whose initial multigraph \(T_0\) has exactly \(n\) vertices. Then the multigraph \(T_{n-2}\) reached after all \(n-2\) contraction steps is a valid output of the algorithm; that is, it has exactly two vertices.

Let \(T\) be a surviving trace of length \(\text{steps}\) over a vertex type \(\alpha \), that is, a family of states \((T_j)_{j \in \mathbb {N}}\) in which each consecutive pair \(T_j, T_{j+1}\) with \(j \lt \text{steps}\) is related by a surviving step. Then for every index \(i\) with \(i \le \text{steps}\), the states \(T_0, T_1, \dots , T_i\) constitute a surviving run of length \(i\) from the initial state \(T_0\) to the state \(T_i\).

Let \(T\) be a surviving trace of length \(\mathrm{steps}\) over a vertex type \(\alpha \): a family of states \((G_j, C_j)\) indexed by \(j \in \mathbb {N}\), in which each consecutive pair below \(\mathrm{steps}\) is joined by a surviving step (the graph \(G_{j+1}\) arises from \(G_j\) by contracting an edge that does not cross the distinguished cut). Then for every index \(i \le \mathrm{steps}\), the number of vertices of the graph at index \(i\) equals the number of vertices of the initial graph at index \(0\) minus \(i\); that is, \(\lvert V(G_i)\rvert = \lvert V(G_0)\rvert - i\).

Let \(T = (G_0, C_0), (G_1, C_1), \dots \) be a surviving trace: a family of states indexed by \(\mathbb {N}\) in which each state at an index below \(\text{steps}\) passes to its successor by contracting some edge of its current multigraph that does not cross its distinguished cut. Suppose the initial cut \(C_0\) is a minimum cut of \(G_0\), and fix an index \(i \lt \text{steps}\) at which the multigraph \(G_i\) has at least two vertices. Writing \(n_i\) for the number of vertices of \(G_i\), \(m_i\) for the number of edges of \(G_i\) (counted with multiplicity), and \(c\) for the size of the initial cut \(C_0\) (its number of crossing edges), one has

Let \(T\) be a surviving trace of \(\mathrm{steps}\) steps, with states \(s_0, s_1, \dots \); write \(G_i\) for the multigraph and \(C_i\) for the distinguished cut in state \(s_i\), and let \(n_i\) and \(m_i\) denote the vertex count and edge count of \(G_i\). Suppose the initial cut \(C_0\) is a minimum cut of \(G_0\), and that \(n_i \ge 2\) for every index \(i \lt \mathrm{steps}\). Then, writing \(c\) for the size of \(C_0\),

the right-hand factors being the one-step survival probabilities for cut size \(c\) and edge count \(m_i\).

Let \(T\) be a surviving trace of length \(\text{steps}\), and for each index \(i\) write \(v_i\) for the number of vertices of the multigraph in its state at index \(i\). Suppose that \(\text{steps} = n - 2\) and that the initial graph has \(v_0 = n\) vertices. Then

where each factor is taken as a real number, the difference \(v_i - 2\) in the left-hand numerator being the truncated subtraction in \(\mathbb {N}\) and the right-hand differences being taken in \(\mathbb {R}\).

Let \(T\) be an indexed surviving trace of length \(\text{steps}\), recording at each index \(i\) a state consisting of a multigraph \(G_i\) together with a distinguished cut \(C_i\), with consecutive states below \(\text{steps}\) related by a surviving step. Then the product of the uniform one-step survival probabilities of the states of \(T\) equals the product, over all \(i \lt \text{steps}\), of the one-step survival probability \(1 - \dfrac {c_i}{m_i}\), where \(c_i\) is the size of the cut \(C_i\) (its number of crossing edges) and \(m_i\) is the total edge count of \(G_i\); that is,

Let \(T\) be an indexed surviving trace of length \(\mathrm{steps}\), with states \(s_0, s_1, \dots \), and write \(c\) for the size of the distinguished cut of the initial state \(s_0\) and \(m_i\) for the edge count of the graph of state \(s_i\). Then the product of the uniform one-step survival probabilities of the states \(s_0, \dots , s_{\mathrm{steps}-1}\) equals

the product of the one-step survival probabilities computed with the initial cut size \(c\) at every index.

Let \(T\) be an indexed surviving trace of \(\text{steps}\) steps, so that \(T\) assigns to each index \(i \in \mathbb {N}\) a state \(T_i\) and, for every \(i \lt \text{steps}\), the passage from \(T_i\) to \(T_{i+1}\) is a surviving step. Then

where \(r(T_i)\) denotes the occurrence-space survival ratio of \(T_i\) (the number of surviving edge occurrences divided by the total number of edge occurrences) and \(p(T_i)\) denotes its uniform one-step survival probability (the number of non-crossing edges divided by the total edge count).