Entropy and Face Dimension of the Perfect-Matching Polytope

Proof. Choose a matching law of mean y_i in each contracted graph. A matching uses exactly one edge at the contracted vertex, so the common coordinates q_e=(y_1)_e=(y_2)_e, e\in C, sum to one. Choose a label e with these probabilities, then draw the two matchings independently from their respective laws conditioned on using e. A label with q_e=0 is never chosen and needs no conditional law.

Remove the contracted vertices and replace the two copies of the chosen crossing edge by its original edge. The internal matchings and this edge cover every original vertex once. The crossing marginals are q_e, and the law of total probability preserves every internal marginal. The resulting matching law therefore has mean y.□

Proof. Denote the set on the right by Q. Every perfect matching has unit degrees and crosses every odd cut, so P(G)\subseteq Q. The degree equation at either endpoint of an edge gives 0\le x_e\le1 for every x\in Q. Thus Q is bounded. If it is empty there is nothing to prove.

We use the elementary fact that a nonempty bounded polytope is the convex hull of its extreme points. Indeed, unless a point is extreme, there is a nonzero direction annihilating all its active constraint rows. The feasible interval in this direction has two endpoints, and the point is a convex combination of them. Each endpoint has a new independent active row: the new row has nonzero directional change, whereas every old active row annihilates the direction. Repeating within the resulting lower-dimensional faces terminates at extreme points.

We show that the extreme points of Q belong to P(G), by induction on the even order. The assertion for order zero is immediate. At order two, Q is the simplex \{x\ge0:\sum_{e\in E}x_e=1\} on the distinguished parallel edges, which is exactly their matching polytope and is empty if there is no edge.

Now let |V|\ge4, and let x be an extreme point of Q. Suppose that an odd set S with 3\le |S|\le |V|-3 has x(\delta(S))=1. Put C=\delta(S), use the two contracted graphs defined above, and let x_i be the restriction of x to the surviving edge labels of G_i.

Both contracted graphs have smaller even order. The degree equations at retained vertices are unchanged, and the degree sum at the new vertex is x(C)=1. To check an odd-cut inequality in a contracted graph, complement its side if necessary so that it excludes the new vertex. The complement remains odd because that graph has even order. Its cut then has exactly the same edge labels and sum as the cut of the corresponding odd set of original vertices. Thus each x_i satisfies the smaller system in Equation (4). By induction, it is the mean of a law on perfect matchings of G_i.

Their crossing coordinates agree, so Lemma 2.1 gives x\in P(G).

It remains to consider an extreme point at which every such nontrivial odd cut is slack. A nonzero vector supported on the positive coordinates of x and preserving all degree equations would allow sufficiently small feasible perturbations in both signs: the positive coordinates stay positive, all nontrivial odd cuts retain positive slack, and singleton cuts and their complements are controlled by the degree equations. Therefore the columns of the unsigned vertex-edge incidence matrix on the positive edges are linearly independent.

Consider a connected component of the positive-edge graph. There are no isolated vertices, by the degree equations. A vertex incident to only one positive edge forces that edge to have value one; its other endpoint then has no other positive incident edge. These vertices therefore occur in isolated edge components. Every remaining component has minimum degree at least two. Column independence implies that its number of edges is at most its number of vertices. Counting incidences forces equality and degree two at every vertex, so the component is a cycle, possibly a two-edge parallel cycle. An even cycle gives a nonzero alternating-sign dependence among the incidence columns. An odd cycle component has cut sum zero on its odd vertex set, contrary to feasibility. Thus only isolated weight-one edge components remain, and x is a perfect matching vector. This completes the induction.□

Proof. Feasibility in both signs forces every active constraint row to annihilate the direction. Conversely, the equations in Equation (5) preserve all active constraints, and sufficiently small perturbations in both signs preserve every inactive inequality, since there are finitely many and each has positive slack. This proves the direction characterization.

The same argument gives a relative neighborhood of x in x+T(x) contained in F_x. Explicitly, for each inactive inequality b_i\cdot y\ge c_i with nonzero normal, choose a radius smaller than its slack at x divided by 2\|b_i\|_2, and take the minimum of these finitely many positive radii. If no such row exists, any positive radius suffices. All active rows stay equalities on x+T(x), and zero-normal rows are constant. Since F_x\subseteq x+T(x), this proves its affine hull and relative interiority.

For any y\in F_x, a short extension from y through x remains in this relative neighborhood. Thus x lies in the relative interior of a segment in F_x having y as an endpoint. Every face containing x must contain y, proving minimality.

Finally, express a point of F_x as a convex combination of matching vectors. Each inequality defining F_x has nonnegative slack at every vector and zero average slack. Every positive-weight vector must therefore belong to F_x. This proves the convex-hull and support assertions. Taking the direction space of this affine hull gives the final equality in Equation (6).□

Proof. We induct on the even order n=2m. At order two, the polytope is the simplex on the distinguished parallel edges. A positive point has dimension |E|-1, giving codimension one as required.

Let n\ge4. If no nontrivial odd cut is tight, positivity and Lemma 2.3 show that only the n degree equations restrict T(x). Thus |E|-d(x)\le n\le3n/2-2. Otherwise choose a tight nontrivial cut C=\delta(S), and let x_i be the restricted means in the two contracted graphs G_i. The feasibility argument in Theorem 2.2 gives x_i\in P(G_i), and every retained coordinate is positive. Put

Each crossing label appears in both graphs, whereas each internal label appears in one. Consequently

Consider the space of compatible directions

Each h_i preserves the degree at its contracted vertex, so \sum_{e\in C}(h_i)_e=0. The linear map (h_1,h_2)\mapsto h_1|_C-h_2|_C therefore takes values in

Since x(C)=1, the set C is nonempty and this target has dimension |C|-1. Its kernel is W, whence

Map (h_1,h_2)\in W to the vector h on the original edges with their internal coordinates and common crossing coordinates. This map is injective: restricting h recovers both h_i. For any such pair, choose \varepsilon>0 so that x_i+th_i\in P(G_i) for both i and every |t|<\varepsilon. Their crossing coordinates agree for each t, so Lemma 2.1 yields x+th\in P(G). Thus h\in T(x) and d(x)\ge\dim W. In particular every parent cut tight at x is preserved, including cuts crossing S, because both signs of the perturbation are feasible.

Using Equation (9) and induction gives

The saving of one compatibility condition is exactly what closes this recurrence at the stated constant.□

Proof. An edge with coordinate one exhausts the degree sum at both endpoints, so neither endpoint meets a fractional edge. At a vertex outside V_f(x), all incident coordinates are zero or one and sum to one; exactly one incident edge therefore has coordinate one. These fixed edges form a perfect matching of V\setminus V_f(x), so |V_f(x)| is even.

Every law of mean x uses each value-one edge and omits each value-zero edge with probability one. Deleting the fixed edges gives a perfect matching law on G_f with mean \bar x, proving \bar x\in P(G_f). Conversely, adjoining the fixed edges to any perfect matching of G_f gives a perfect matching of G.

The inequalities 0\le y_e\le1 hold throughout P(G), so requiring any of these coordinates to equal zero or one defines a face; their intersection Q_x is a face containing x. The preceding matching extension shows \iota(P(G_f))\subseteq Q_x. For the reverse inclusion, express any point of Q_x as a law on perfect matchings. Its fixed zero and one marginals force every positive-probability matching to omit the zero edges and contain the fixed edges. Removing those edges leaves a perfect matching of G_f. This proves both equality of the image with Q_x and the stated bijection of laws for every mean. Coordinate restriction is the affine inverse of \iota.

An affine isomorphism preserves faces and their relative interiors. The image of the minimal face at \bar x is thus a face of Q_x, and hence of P(G), containing x in its relative interior. By Lemma 2.3, it is exactly F_x. In particular, their dimensions are equal. One can also see this directly on directions: a two-sided direction at x vanishes on every fixed zero or one coordinate, and its restriction to E_f(x) is a two-sided direction at \bar x; extension gives the inverse correspondence.

If m_f\ge1, every coordinate of \bar x is positive, and Proposition 2.4 applied to G_f gives

If m_f=0, all coordinates of x are integral, and the degree equations identify x as a single matching vector. Finally, at every vertex of V_f(x) the fractional incident coordinates sum to one. Summing those degree equations counts each fractional edge twice and gives \sum_{e\in E_f(x)}x_e=m_f.□

Proof. The laws of a prescribed mean form a nonempty closed subset of the finite probability simplex. Compactness and continuity of entropy give attainment. Mixing maximizing laws proves concavity, and entropy is nonnegative.

For upper semicontinuity at x, let y_j\to x in P(G) and choose maximizing laws at y_j. Take a subsequence realizing the upper limit of their entropies and then a convergent subsequence of laws. Its limit has mean x, so continuity of entropy on the simplex gives \limsup_j H(y_j)\le H(x).

For lower semicontinuity, take y\ne x close to x in P(G) and put t=\sqrt{\|y-x\|_2} and z=x+(y-x)/t. For sufficiently close y, we have 0<t<1 and z\in P(G). To check the latter assertion, use the finite linear description of the polytope. Equalities are preserved; an inequality tight at x is preserved because its slack at z is its slack at y divided by t; and every inactive inequality stays satisfied since z\to x. There are only finitely many inactive inequalities. Since y=(1-t)x+tz, concavity and nonnegativity give H(y)\ge(1-t)H(x). Letting y\to x proves the reverse semicontinuity.□

Proof. The active inequalities defining F_x have nonnegative slack at each matching vector. Their expected slack is zero at x, so every positive-probability atom belongs to F_x. The geometric description also shows that F_x=\conv\mathcal A_x and that x is relatively interior to it.

Let b be the barycenter of \mathcal A_x. For sufficiently small \varepsilon>0, the point (x-\varepsilon b)/(1-\varepsilon) belongs to F_x. Represent it by a law on \mathcal A_x and mix in weight \varepsilon of the uniform law. This produces a law q of mean x positive on every face atom. If a maximizing law p vanished on a nonempty set Z\subseteq\mathcal A_x, then

for sufficiently small u>0. The summands outside Z are differentiable at p_a>0, which justifies the O(u) term. Thus p is positive.

Form the matrix with columns (1,a), indexed by a\in\mathcal A_x. All sufficiently small perturbations of p in its kernel preserve positivity, mass and mean. The entropy gradient (-1-\log p_a)_a therefore lies in the row space. Because the constant row is present, \log p_a=c+\theta\cdot a for finite real coefficients; normalization gives Equation (14). No independence of the constraint rows is required.

For a law of the displayed form with parameter \eta, all face atoms have positive probability. An inequality is tight at its mean y exactly when it is tight at every atom of \mathcal A_x, equivalently when it is tight at x. Hence F_y=F_x, and every law q' of mean y is supported on \mathcal A_x. Equation (13) gives

with equality for the exponential law itself. This proves maximality.□

Proof. Let p and \theta be supplied by Lemma 3.2, and write T=\operatorname{span}(F_x-x). For v\in\R^E and real t, set

The lemma gives F_{y(t)}=F_x and

All sums are finite, so these curves are smooth. Every coordinate of y(t) remains strictly between zero and one, since both coordinate values occur among the positive-probability face atoms.

Define the covariance matrix

Differentiation gives p_a'(0)=p_a v\cdot(a-x) and y'(0)=Kv. For every w, we have w^{\mathsf T}Kw=\sum_a p_a(w\cdot(a-x))^2. Positivity of p and the spanning of T by a-x therefore give

Also y''(0)\in T, since the curve stays in x+T.

Let g=\nabla J_c(x) and let D be its diagonal Hessian:

Since \Phi'(t)=v\cdot y(t), Equation (16) gives \frac{d}{dt}H(y(t))=-(\theta+tv)\cdot y'(t). For r(t)=J_c(y(t))-H(y(t)), the first two derivatives at zero are

Stationarity gives r'(0)=0 for every v. Since \operatorname{im}K=T and y''(0)\in T, the last term in r''(0) vanishes. The second derivative test is therefore

This cancellation is why differentiating within the minimal face suffices; no smoothness of H across different faces has been assumed.

Take orthonormal eigenvectors u_1,\ldots,u_d of K with positive eigenvalues \lambda_1,\ldots,\lambda_d. Substituting v=u_i in Equation (18), dividing by \lambda_i, and summing gives

Only the spectral decomposition of K is used; K and D need not commute. If d=0, this same statement is the empty sum identity. Each coordinate is Boolean, so K_{ee}=x_e(1-x_e). Using \sum_e x_e=m, we obtain

which proves Equation (15).□

Lower bound in Theorem 1.1. Write the original vertex count as 2M\ge2, and fix c=2-2/M+\varepsilon with \varepsilon>0. By Lemma 3.1, J_c-H attains a maximum on P(G). Suppose that this maximum is positive, at x. Delete its zero edges and the endpoints of its value-one edges. The exact fractional reduction in Lemma 2.5 identifies all laws of mean x with laws of the reduced mean and preserves F,B,H. An empty reduction would give F=B=H=0, contrary to positivity. The reduced graph therefore has 2m vertices for some 1\le m\le M, and all retained coordinates are strictly fractional.

Every feasible mean in the reduced graph extends by the fixed matching edges to a feasible original mean, preserving the same three functions. The reduced mean consequently remains a global maximum of J_c-H. The geometric rank bound gives d\ge s-3m+2, whereas Lemma 3.3 gives

This contradiction proves H\ge F-cB for every \varepsilon>0. For each fixed mean, B is finite; letting \varepsilon\downarrow0 proves H\ge F-(2-2/M)B. The strict coefficient followed by this limit is essential: the displayed geometric comparison can be an equality when m=M and \varepsilon=0.□

Upper bound in Theorem 1.1. Let X=(X_e)_{e\in E} be the incidence vector of any matching law with mean x, and order E. For a vertex v, the chain rule gives

Conditioning on additional finite random variables decreases conditional entropy, by concavity of entropy applied to the conditional laws. Every edge, including every labelled parallel edge, belongs to exactly two vertex stars. Summing and applying the chain rule again therefore gives \sum_v\Ent(X_{\delta(v)})\ge2\Ent(X). At a vertex the star vector makes exactly one choice, with probabilities (x_e)_{e\in\delta(v)}, so

Taking the maximum over laws proves the upper bound, including fixed coordinates and disconnected graphs.□

Proof. The exact reduction preserves the functions. Every residual component has a perfect matching, hence even positive order. A law of a whole matching induces matching laws on the components, whose entropies sum to at least the joint entropy. Conversely, the independent product of component maximizing laws realizes the prescribed mean and the sum of their entropies. Thus H, like F and B, is additive at these fixed component means. Apply Theorem 1.1 separately to each component.□

Proof. The first inequality follows from H\le F. Nonnegativity of entropy gives F-H\le F, while Equations (19) and (21) give F-H\le(2-2/m)B\le2m-2. This includes m=1, when the defect is zero.□

Proof. The entropy comparison in Equation (13), applied to the uniform law, gives entropy at most \ln N for every law on N outcomes, with equality for the uniform law. At the mean \bar x of the uniform matching law we therefore have H(\bar x)=\ln N. Equation (19) gives \ln N\le F(\bar x)\le H_{\mathrm{bin}}(\bar x), proving both lower estimates. Corollary 4.1 gives F(x)\le H(x)+2m-2\le\ln N+2m-2 at every x\in P. Also,

Taking maxima proves the upper estimates. The maxima exist because P is compact and both separable functions are continuous.□

Proof. Let M_1,\ldots,M_k be the selected matchings and take their uniform mixture. Its mean

is 1/k on their union of km labeled edges and zero on every other edge. In particular, the hypotheses do not require all ambient edges to belong to that union. We have F(x)=m\ln k. If k=1, the selected matching already gives N(G)\ge1. For k\ge2, direct evaluation yields

Since H(x)\le\ln N(G), Theorem 1.1 now gives

Exponentiating proves the first inequality in Equation (25). The function \ln(1-u)+u/(1-u) starts at zero and has derivative u/(1-u)^2\ge0 for 0\le u<1. Thus (k-1)\ln(1-1/k)\ge-1, giving the second inequality; the third uses m-1\le m.□

Proof. The vector x_e=1/k has unit degree sums, and the cut hypothesis gives x(\delta(S))\ge1 for every odd S. Theorem 2.2 implies x\in P(G); in particular, G has a perfect matching. Since |E|=km, the evaluations of F(x) and B(x) in the preceding proof apply unchanged when k\ge2. For k=1, the graph itself is a perfect matching.

For the final assertion, an odd S is nonempty and proper because |V(G)| is even. Edge connectivity gives \lvert\delta(S)\rvert\ge k-1, while summing degrees in S gives

Consequently |\delta(S)|\equiv k\pmod2; it cannot equal k-1 and is therefore at least k. Parallel edges are counted with multiplicity in this identity.□

Proof. Every perfect matching of G' crosses the odd cut \delta(T) either once or three times. Hence y(\delta(T))\ge1 is valid on P(G'), and its equality set is a face. A convex combination lies in this face exactly when every matching with positive coefficient crosses the cut once. For these matchings the extension and contraction just described are inverse bijections, and the indicator of f_i equals the indicator of e_i. They therefore induce the stated affine isomorphism, with inverse given by restriction to the old edge labels.

The coordinate statement follows directly. Finally, Q_T is a face containing x'. The minimal face of P(G') at x' is therefore also the minimal face of Q_T at x'; affine isomorphisms preserve minimal faces.□

Proof. For m=1, the three matching vectors are the three coordinate vectors in \mathbb R^3, and P(G_1) is their simplex. Its uniform point is in its relative interior. Repeated application of Lemma 5.1 shows that the minimal face at x^{(m)} is the image of this simplex, with vertices a(M_1),a(M_2),a(M_3). In particular its dimension is two.

One can also see the restriction on laws directly. For the last inserted triangle, a law with edge marginals 1/3 has expected cut-crossing count 3(1/3)=1. Since each matching crosses this cut once or three times, it must cross once almost surely. Contraction gives a law on the preceding graph with the same uniform marginals, and the crossing-one extension is unique. Iterating leaves only the three initial matchings. Thus the original law is supported on M_1,M_2,M_3. Since these matchings partition the edges, the marginal of any edge in M_i equals the probability assigned to M_i, which must be 1/3. This proves uniqueness and the entropy formula.

There are 3m edges, all with marginal 1/3. Substitution in the definitions of F and B gives the remaining formulas.□

Proof. Applying the asserted inequality to G_m,x^{(m)} gives

Let m tend to infinity. The graphs with m\ge2 are simple, so the same limit applies under that restriction.□

Proof. Let p_\beta(M)=2^{\beta\cdot\mathbf1_M}/Z_\beta, a positive probability law on the matching family. The finite entropy comparison with this law gives, for any matching law p of mean x,

with equality for p=p_\beta. Indeed, this is the nonnegativity of \sum_{M:p(M)>0}p(M)\ln(p(M)/p_\beta(M)), which follows from \ln t\le t-1. Taking a maximizing law at each mean and then the maximum over means therefore yields

Corollary 4.1 says F(x)-(2m-2)\le H(x)\le F(x). Divide by \ln2, add \beta\cdot x, and maximize to obtain Equation (28).□

Proof. With n=2m, Corollary 6.1 gives

Since \ln2=\int_1^2t^{-1}\,dt\ge1/2, we have (n-2)/\ln2\le2n-4\le4n. Enlarging both sides of this bracket proves the claim.□

Proof. For each pair with k_e>0, put r_e=2^{\lfloor\log_2 k_e\rfloor}. Then

For a valid matching of K_n, the product of its k_e’s is the number of corresponding perfect matchings in the input multigraph. Replacing these n/2 factors by r_e and summing therefore gives

If N>0, there is at least one valid matching, and its rounded weight is a positive integer. Hence Z_{\mathrm{good}}\ge1.

Every remaining matching uses a pair of weight 2^{-L}, and each of its other pair weights is at most 2^{b_{\max}}. There are at most 2^p matchings, since each is a subset of the p pairs. Thus

For the last inequality, put t=n+b_{\max}+1\ge5 and note that

When N=0, every term is in Z_{\mathrm{bad}}; also Z_\beta>0 because K_n has a perfect matching and every assigned weight is positive. This proves the first implication in Equation (32). When N>0, Equation (33) gives the lower bounds, while

because N is a positive integer.□

Proof. At a positive knot, \phi(2^{-k})=k2^{-k}. The chord between 2^{-(k+1)} and 2^{-k} therefore has slope k-1 and intercept 2^{-k}, whereas the chord from zero has slope K. This proves Equation (34). Reading the intervals from left to right, the slopes are nonincreasing, so \psi is concave. Since p\ge6, we have K\ge1, and all its slopes lie between -1 and K.

The concavity of \phi puts every chord below its graph. If 2^{-(k+1)}\le t\le2^{-k}, then

Consequently 0\le\phi(t)-\psi(t)\le t on this interval. On the interval adjacent to zero, write t=2^{-K}r, where 0\le r\le1. Then

Here the expression at r=0 is interpreted by continuity; on (0,1], differentiation gives the maximum 1/(e\ln2)<1.

For x\in P, summing the degree equations gives \sum_e x_e=n/2. Apply the bound x_e on intervals above 2^{-K}, and the bound 2^{-K} on the interval below it. The total error is at most

This proves Equation (35).□

Proof. Write w=w(x), d_i=1-x(\delta(i)), and d_{\mathrm{tot}}=\sum_{i\in V}d_i. Correct the degrees by setting

The correction sums to d_i at vertex i, since

Thus x'(\delta(i))=1 for every i. Since |d_i|\le w and |d_{\mathrm{tot}}|\le nw,

Consequently x'_e\ge-2w, and every odd set S satisfies

Let u_{ij}=1/(n-1). This vector has degree sums one, and

Cuts with |S|=1 or |S|=n-1 have value one. For every nontrivial odd cut, 3\le |S|\le n-3, and hence, when n\ge6,

There are no nontrivial odd cuts when n=4. In particular, u\in P.

Set

If A_0w\ge1, including equality, then y=u\in P. Otherwise t=A_0w<1. The inequalities

give

Equation (40) also gives, for each nontrivial odd cut,

The degree sums remain one, so the trivial odd cuts also have value one. Theorem 2.2 now yields y\in P in this branch as well.

For either branch, use the identity

Both u and x lie in the box, so

This also covers w=0.□

Proof. By Lemma 7.2, the slopes of \psi are integers of absolute value at most K. Since |\beta_e|\le L, it follows that

For the point y\in P supplied by Lemma 8.1, Equation (43) gives

Conversely, \Phi=f on P, proving equality of the maxima. The function w is a maximum of affine functions and is therefore convex. Since f is concave, \Phi is concave.

Choose a supporting piece slope \sigma_e of \psi at each x_e; at a knot either adjacent slope is allowed. With b_e=\sigma_e+\beta_e, these choices give

Write each absolute value in Equation (38) as the maximum of its two affine terms. Choose any active affine term a\cdot z+c in this maximum, including the zero term when it is active. Then a_e\in\{-1,0,1\}, and

Subtracting the last inequality, multiplied by M_0, proves that g=b-M_0a is a supergradient of \Phi on the entire box. The independent choices of supporting pieces and active rows are valid also at endpoints and ties. Finally, g is integral and

□

Proof. Choose z\in P with f(z)=f^*; then \Phi(z)=f^* by Lemma 8.2. Clipping cannot increase distance to z\in[0,1]^p. Expanding the squared distance and using the supergradient inequality therefore gives

Summing Equation (46) over exactly the indicated N_{\mathrm{it}} indices yields

Here \|x^{(0)}-z\|_2^2\le p. Thus the largest of the sampled values, say V, satisfies f^*-1\le V\le f^*. Since R=\lfloor V\rfloor,

which proves Equation (45).□

Proof. Maintain integers b_{ij}=-b_{ji} such that b_{ij}\le c_{ij} in both directions and \sum_j b_{ij}=0 for i\notin\{a,b\}. The two directional inequalities give -c_{ij}\le b_{ij}\le c_{ij}. Start with zero flow. If a simple directed path from a to b uses only steps with residual capacity c_{ij}-b_{ij}>0, increase the flow on each forward step by one and decrease its reverse by one. Integrality makes this feasible, conservation is preserved, and the net source outflow q=\sum_j b_{aj} increases by one. Since

there are at most C augmentations.

When no such path exists, let S be the vertices reachable from a by positive-residual steps. Then b\notin S, and every step from S to its complement is saturated. Antisymmetry cancels internal flows, so conservation gives

For every other a–b cut, the same conservation identity and b_{ij}\le c_{ij} give capacity at least q. Thus S is minimum. A graph search with fixed vertex order finds a simple residual path, or the final reachable set, in O(v^2) operations. There are at most C+1 searches, and all flows and residual capacities have magnitude at most 2C. The argument includes C=0.□

Proof. Call a cut terminal-separating if both sides meet U. Compute a minimum cut for every pair of distinct terminals using Lemma 9.1, and take the least-capacity result, with sides A and \overline A=W\setminus A. This is a minimum terminal-separating cut: every such cut separates some terminal pair, and every recorded pair cut is terminal-separating.

If |A\cap U| is odd, return A. Every admissible odd-terminal cut is terminal-separating, so this answer is optimal. Otherwise both A\cap U and \overline A\cap U have positive even cardinality. Form two children:

1. (i)

   keep A, contract \overline A to a new nonterminal, and use terminal set A\cap U;

2. (ii)

   keep \overline A, contract A to a new nonterminal, and use terminal set \overline A\cap U.

For example, in the first child the capacity from i\in A to the new vertex is \sum_{j\in\overline A}c_{ij}. Recurse on both children and return the better lifted cut. Every call strictly decreases the positive even terminal count; when |U|=2, the first cut is already odd.

Lifting cuts. A child cut lifts by replacing its contracted vertex, if included, with the entire block it represents. The crossing capacities are unchanged, and including that block adds an even number of parent terminals. Thus the lift has the same capacity and is terminal-odd.

This remains true through arbitrarily nested contractions. Relative to the initial instance, current vertices form a partition into blocks. Every current terminal is an original terminal singleton, and every nonterminal block contains an even number of original terminals. Initially the latter count is zero; each contraction combines an even number of current terminals with blocks of even parity, preserving the assertion. Capacities between current vertices are sums of original capacities between their blocks. Consequently every returned subset lifts to an original subset with the same capacity and terminal parity. Figure 2 illustrates the parity rule.

Preserving an optimum. Let S be an optimal odd-terminal side in the current instance. Exactly one of S\cap A and S\cap\overline A contains an odd number of terminals; exchange the names of the two sides so that it is S\cap A. Because |A\cap U| is even, replacing S by its complement preserves this odd intersection. Make this replacement if S contains all terminals of \overline A. Now S\cup A contains terminals of A and omits a terminal of \overline A, so

For any two vertex sets, nonnegative undirected capacities satisfy

Indeed, the right side minus the left side is twice the capacity between S\setminus A and A\setminus S. It follows that c(S\cap A)\le c(S). The set S\cap A is a feasible odd-terminal side in the first child, avoiding its contracted vertex. Hence at least one child has optimum at most the parent’s. Conversely, lifting shows that every child optimum is at least the parent’s. Induction on |U| proves that the better recursive answer attains the parent optimum.

Size and running time. Each nonleaf splits its terminal set into two disjoint nonempty even sets. There are at most |U|/2 leaves and hence at most |U|-1 instances in this binary recursion tree. Each contracted side contains at least two terminals, so a child also has fewer vertices than its parent. Within any one instance, every surviving capacity sums a disjoint set of original edge capacities; original edges internal to blocks are discarded. Its total capacity is therefore at most C. Capacities in different children may overlap, and we account for them by multiplying the cost of an instance by the number of instances.

There are at most O(|U|^2) pair computations per instance, each costing O(v^2(C+1)) by Lemma 9.1. Contractions and lifted-set bookkeeping fit within the same bound. This proves the stated running time. All comparisons and tie choices may use fixed orderings; zero capacities require no perturbation.□

Approximation guarantee in Theorem 1.2. The elementary cases return the exact count, so suppose n\ge4 is even and the algorithm reaches the optimization. Lemma 8.3, Lemma 7.2, and Corollary 6.2 give, respectively,

Combining them yields

If N=0, Lemma 7.1 gives \log_2 Z_\beta\le-20n, hence R\le-16n<-10n. If N>0, the same lemma gives Z_\beta\ge1, hence R\ge-3n>-10n. Thus the zero test is exact.

Now let N>0. The inequalities Z_\beta\le2N and Z_\beta\ge2^{-n/2}N, again from Lemma 7.1, imply

Also \log_2N\ge0, so \rho=\max\{0,R-5n\}\le\log_2N. Since \rho\ge R-5n, Equation (49) gives \log_2N-\rho\le9n. Exponentiating proves A\le N\le2^{9n}A=512^nA.□

Proof. The elementary cases require only integer operations on the input. In the remaining case put \tau=n+b_{\max}+1, so \tau\ge5. The parameters have polynomial numerical magnitude, not just polynomial bit length. Indeed p\le\tau^2, K\le n\le\tau, 2^K<2p, L=100\tau^3, and A_0\le10\tau^2. Consequently

Here K+L\le101\tau^3 and 2+A_0\le12\tau^2 give the first inequality, and K+L+M_0\le1313\tau^7 gives the second. The exponent of each positive multiplicity is obtained from its binary length: \lfloor\log_2 k_e\rfloor=\operatorname{bitlen}(k_e)-1. No logarithm is evaluated numerically.

The update preserves a_e^{(j)}\in\{0,\ldots,D_0\}, because every supergradient coordinate is integral. Thus every iterate has denominator dividing D_0. On a noninitial dyadic interval the affine formula for \psi is (k-1)t+2^{-k}, and on the interval next to zero it is Kt. The intercept denominators therefore divide 2^K. Every degree or cut sum, and hence w(x^{(j)}), has denominator dividing D_0. A single common denominator for all trial objectives is

This denominator does not grow with the number of iterations or with changes of dyadic piece. The piece comparisons, objective comparisons, and the final floor can all be made by exact integer arithmetic.

For an explicit bound on the operands, 0\le w(x)\le n on the box, and

Together with Equation (50) and 2^K<2p, these bounds show that all objective numerators with denominator Q have polynomial magnitude in \tau. The supergradients, scaled capacities, and counters do as well. Their bit lengths are therefore O(\log\tau).

At any trial point, the cut oracle receives capacities a_e^{(j)}, not the original multiplicities. Their total is at most pD_0. After any sequence of contractions, each surviving capacity is a sum of original capacities between two disjoint vertex blocks; internal edges are discarded. Every original edge contributes to at most one surviving pair, so the same total bound holds throughout the recursion. By Lemma 9.1, each terminal-pair computation uses at most pD_0 unit augmentations. Lemma 9.2 uses O(n) recursive calls, each with O(n^2) terminal-pair computations. Dense residual path searches take O(n^2) elementary operations. The entire optimization thus uses at most

elementary graph and arithmetic operations, on integers of O(\log\tau) bits. Standard integer arithmetic gives a polynomial bit bound.

It remains to bound the length of the explicit integer output. Lemma 8.3 gives R\le f^*. Since \psi(t)\le -t\log_2t\le1 on [0,1], \beta_e\le b_{\max}, and \sum_e x_e=n/2 on P(K_n), we have f^*\le p+b_{\max}n/2. This upper bound is nonnegative, so the clamped exponent satisfies

Writing 2^\rho as a binary integer therefore takes O(n^2+nb_{\max}+1) bits and operations. The zero and exact elementary outputs also have polynomial length.

For an explicit vertex list, both n and b_{\max} are bounded by the input bit length. The same conclusion holds when n is given in binary and only positive pair records are listed. The coverage test in Step 1 takes polynomial time in the input bit length. If it does not return zero, every vertex appears in a record, so n is at most twice the number of positive pair records. Thus the complete-pair allocation and the optimization are polynomial in this encoding as well.□

Proof. First let A,B\in\mathcal S_x cross, and put

The first three regions are nonempty; O may be empty. If |I| is odd, then both I and A\cup B are odd, and the coordinatewise cut identity is

Here E(D,D') denotes the edges joining those two regions. Taking the dot product with x, the left side equals two, the first two terms on the right are at least one each, and the last term is nonnegative. Thus both new odd sets are tight and x(E(D,D'))=0. Since every coordinate of x is positive, there are no edges in E(D,D'), so its indicator vector vanishes.

If |I| is even, then D,D' are odd and instead

The same argument shows that D,D' are tight and that the last indicator vanishes. Both identities hold edge by edge, including for parallel edges. All replacement sets are nonempty and proper: in the first case A\cup B is odd and so cannot be the even set V, and in the second case the differences are nonempty proper subsets. In particular, if A\cup B=V, only the second case can occur. We have proved that in either case the two replacements U,W belong to \mathcal S_x and satisfy

Choose an inclusionwise maximal laminar subfamily \mathcal L of \mathcal S_x with independent cut vectors, and let R be their span. Suppose a tight cut vector lies outside R. Among the corresponding tight sets choose A crossing as few members of \mathcal L as possible. It crosses some B\in\mathcal L, for otherwise it could be added to the family while preserving both laminarity and independence. Uncross A,B as above. At least one replacement vector lies outside R, since otherwise Equation (55) and \chi_B\in R would give \chi_A\in R.

Each replacement is laminar with B. Also, neither replacement can cross a member C\in\mathcal L that did not cross A. Indeed, such a set C is laminar with both A and B. If C contains A, then it meets B, and laminarity forces it to contain B as well: the other nesting direction would imply A\subseteq B. Thus C contains A\cup B. If C\subseteq A, laminarity with B puts C inside I or D; it cannot contain B, since B\nsubseteq A. Finally, if C is disjoint from A, its relation to B puts it inside D' or O. These cases exhaust the possibilities. Every set among I,A\cup B,D,D' is laminar with each set in this classification.

Consequently the replacement whose vector is outside R crosses only previously crossed members of \mathcal L, and it no longer crosses B. This contradicts the minimal crossing count of A. Hence \mathcal L spans every tight cut vector.□

Laminar proof of Proposition 2.4. Take the laminar spanning family from Lemma A.1. Adjoin all singleton sets, if missing, and then adjoin V as a root. The resulting inclusion tree has 2m singleton leaves. Each internal node is the disjoint union of its children, because all singletons are present. Every proper node has odd cardinality. A nonroot internal node therefore has an odd number of children, at least three. The root has an even number c of children, at least two.

If q is the number of nonroot internal nodes, the tree identity for the number of leaves gives

Hence the number of proper nodes is 2m+q\le3m-c/2. If c\ge4, their cut vectors have rank at most 3m-2 by this count. If c=2, the two root children are complementary sets, and their cut vectors coincide. The rank is then at most the number of proper nodes minus one, again at most 3m-2. The original laminar spanning family is contained among these proper nodes. Equation (7) now proves the claim.□

Proof. Identify T(x) with a subspace U_x of \mathbb R^A. We prove the sharp estimate by induction on the even order n. At order two, the supported matching polytope is a simplex, whose positive point has codimension one. For n\ge4, if no nontrivial odd cut is tight, only the degree equations constrain U_x. Thus its codimension is at most n\le3n/2-2.

Otherwise choose a tight nontrivial cut \delta(S). Contract each side in turn as in the main geometric proof, obtaining x_i\in P(G_i), supported edge sets A_i=\{e:(x_i)_e>0\}, and direction spaces U_i=T(x_i)\subseteq\mathbb R^{A_i}. The restrictions are feasible by the odd-cut check in the proof of Theorem 2.2. The orders satisfy 4\le n_i<n and n_1+n_2=n+2. Let C=A\cap\delta(S); this set is nonempty since x(C)=1. Every label in C occurs in both A_i.

Let r_i:\mathbb R^A\to\mathbb R^{A_i} restrict coordinates, and define

For u\in\ker\mathcal Q, both restrictions are child face directions. Choose a common positive radius such that x_i+t r_i(u)\in P(G_i) in both signs of t. The perturbed means agree on every cut coordinate. Lemma 2.1 glues them to give x+tu\in P(G), so \ker\mathcal Q\subseteq U_x. In particular, all tight parent cuts are preserved, including those crossing S: their nonnegative slacks cannot change in opposite signs under these two feasible perturbations.

There is one dependence between the two quotient requirements. The cut-sum functionals

are well-defined because every child direction preserves the degree of the contracted vertex. Each is nonzero, as the class of a unit vector on any cut label has value one. For every u\in\mathbb R^A,

Thus the image of \mathcal Q lies in the kernel of the nonzero functional (v_1,v_2)\mapsto\ell_1(v_1)-\ell_2(v_2). This kernel has codimension one in the full quotient target. Rank–nullity and induction now give

For n\ge4, this is at most 2(n-2). The order-two simplex and the empty graph give the remaining assertions.□

Proof. An edge with value one exhausts the degree equation at both its endpoints, so neither endpoint meets a fractional edge. Conversely, at a vertex outside V_f(x), all incident coordinates are zero or one and sum to one. Exactly one of those edges has value one. Thus the vertices outside V_f(x) are covered by disjoint fixed edges, and s_f is even.

Let H be the graph with vertex set V_f(x) and edge set E_f(x), and let \bar x be the restriction of x to E_f(x). A matching law with mean x uses every value-one edge and no value-zero edge with probability one. Deleting the fixed edges therefore gives a perfect matching law on H with mean \bar x, whose coordinates are all positive. Conversely, adjoining the fixed edges to any perfect matching of H gives a perfect matching of G. This affine extension of P(H) into P(G) sends \bar x to x, and its linear part injects the two-sided direction space at \bar x into T(x).

If s_f\ge 4, Proposition A.2 now gives

If s_f=2, the residual graph consists of k=|E_f(x)|\ge 2 distinguished parallel edges. Its polytope is the simplex \{z\ge 0:\sum_e z_e=1\}, and the positive point \bar x has direction dimension k-1. Hence d(x)\ge k-1=|E_f(x)|-1. If s_f=0, the point is a matching vector and the dimension inequality is immediate; the minimal face is the singleton consisting of that matching vector.

Finally, each vertex of V_f(x) has total fractional incident value one. Summing these degree equations counts each fractional edge twice, giving the second identity in Equation (58).□

Proof. The empty graph gives the stated trivial case. Assume n\ge2. For the upper bound, regard a matching law with mean x as a law on \{0,1\}^E, giving zero probability to nonmatching vectors. Compare it with independent Bernoulli coordinates of respective means x_e. This product law is positive wherever the matching law is positive: a coordinate with mean zero or one is necessarily fixed at that value under both laws. Equation (13) now gives the upper bound.

For the lower bound, fix either c=3 or c=4. Lemma 3.1 and continuity of J_c imply that H-J_c attains its minimum on the compact set P. At an integral mean the only possible law is the point mass at that matching vector, so H=J_c=0. It suffices to rule out a fractional minimizer.

Suppose, then, that x is such a minimizer. Take its positive maximizing law p and a parameter \theta from Lemma 3.2. For any v\in\mathbb R^E and t\in\mathbb R, define

The same lemma shows that x(t) stays in the relative interior of F_x and

Thus we may differentiate along these curves without assuming differentiability of H across faces.

Let

be the covariance matrix at t=0. Differentiating the finite sums gives p_a'(0)=p_a\,v\cdot(a-x), hence x'(0)=Cv. For any w\in\mathbb R^E,

All p_a are positive, and \operatorname{span}\{a-x:a\in\mathcal A_x\}=T(x). Since C is symmetric, it follows that

At a fractional mean, some coordinate has variance C_{ee}=x_e(1-x_e)>0, so d(x)\ge1. Also x''(0)\in T(x), because the whole curve lies in \operatorname{aff}F_x=x+T(x).

On the fractional coordinates, write

let D be diagonal, and set g_e=D_{ee}=0 on the other coordinates. These entries represent the derivatives of J_c restricted to the face. Indeed, a coordinate with x_e\in\{0,1\} has that value on every face atom, so its contribution to J_c(x(t)) is constantly zero. A fractional coordinate takes both bit values among the face atoms; positivity of p(t) keeps 0<x_e(t)<1 for every finite t. Consequently the usual chain rule on fractional coordinates gives all derivatives of J_c(x(t)).

From \Phi'(t)=v\cdot x(t) and Equation (60), we obtain

Both signs of t are permitted. The minimum property at t=0 therefore gives

By Equation (61), \theta+g is orthogonal to T(x), and in particular (\theta+g)\cdot x''(0)=0. The second derivative at the minimum is accordingly

Let u_1,\ldots,u_d be orthonormal eigenvectors for the positive eigenvalues \lambda_1,\ldots,\lambda_d of C, where d=d(x). Substituting v=u_i in Equation (62) and dividing by \lambda_i>0 gives \lambda_i u_i^{\mathsf T}(-D)u_i\ge1. Summing and using C=\sum_{i=1}^d\lambda_i u_i u_i^{\mathsf T}, we find

Only the spectral decomposition of C is used here; no inverse of C, or simultaneous diagonalization of C and D, is needed.

Each matching coordinate is Boolean, so C_{ee}=x_e(1-x_e). Writing s_f for the number of vertices incident with E_f(x), Corollary A.3 gives

For c=4, the weaker consequence d(x)\ge|E_f(x)|-2s_f of the residual dimension bound suffices:

because a fractional point has s_f>0. For c=3, the trace is |E_f(x)|-2s_f, so we use the exact residual cases. If s_f\ge4, then

If s_f=2, then

These exhaust the positive even values of s_f. For either coefficient, the result contradicts Equation (63). Thus no fractional minimizer exists; the minimum is attained at an integral mean and equals zero. This proves the lower bound for each coefficient by its own covariance contradiction.□

Proof. Theorem A.4 proves F-3B\le H\le F+B by the contraction and covariance route; its coefficient-four proof gives F-4B\le H as well. Since B\ge0, the first two terms are ordered as displayed. Nonnegativity of entropy and B\le m give F-H\le\min\{F,3m\}. Put t=F(x)/m\ge0 and f(t)=8(1-e^{-t}). On [0,\ln2], one has f(0)=0 and f'(t)=8e^{-t}\ge4\ge1, hence f(t)\ge t. For t\ge\ln2, one has f(t)\ge4\ge3. Thus \min\{t,3\}\le f(t), proving the nonlinear inequality including t=0. This deduction is independent of the normalized inverse-covariance proof of Theorem B.1.

For the optimized bound, H\le\ln N and (F+B)-(F-3B)=4B\le4m=2n give the upper error 2n. Using F-4B instead gives the separate original comparison (F+B)-(F-4B)=5B\le5m=5n/2. The uniform matching law supplies the lower bound exactly as in Corollary 4.2. The sharper error 3m-2 in that corollary improves both comparisons on the same domain.□

Proof. For the selected matching mixture in Theorem 4.3, F(x)=m\ln k and x vanishes outside their labelled union. For k\ge2, F(x)-3B(x)=m\ln k+3m(k-1)\ln(1-1/k). Using H(x)\le\ln N(G) and the coefficient-three inequality in Corollary A.5, then exponentiating, gives the first bound. The inequality (k-1)\ln(1-1/k)\ge-1 from the proof of Theorem 4.3 gives its coarse form. At k=1 the selected matching gives N(G)\ge1=b_1^m.

At this same mean, the nonlinear inequality gives \ln N(G)\ge m\ln k-8m(1-1/k), including k=1. Exponentiating and using 1-1/k\le1 proves the second line. For a regular graph satisfying the odd-cut hypothesis, Corollary 4.4 proves that the uniform vector is feasible; the same evaluations then prove both statements without requiring a partition of the edges into perfect matchings. Its cut-parity argument also proves the (k-1)-edge-connected even-order case.□

Proof. The partition provides the hypothesis of Corollary A.6; its uniform law has marginal 1/k on every ambient edge. Thus the nonlinear proof just given applies verbatim. For k=1 the entire graph is a single perfect matching. For k=0 it has no edges. The empty case follows directly from the definition of a matching and does not use expressions containing 1/m.□

Proof of Theorem B.1. Define

Suppose that \Psi is positive somewhere. By Lemma 3.1, it has a positive maximum at some x\in P. Let F_x be the minimal face containing x, and put

Here s counts supported edges. Each matching has exactly m edges, so \sum_ex_e=m and 0\le x_e\le1. Concavity of -u\ln u gives

On [0,\ln8], we have f(0)=0 and f'(t)\ge1, so f(t)\ge t. Since H(x)\ge0, positivity of \Psi(x) therefore forces t>\ln8, and hence s>8m. The supported-face estimate of Proposition A.2 now yields

Thus all integral and low-entropy cases have already been excluded before any covariance inverse is introduced.

Let

Every law whose mean is in F_x is supported on \mathcal M_x. Indeed, each inequality active on this face has nonnegative slack at every matching vector. Expected slack zero forces every atom of positive probability to satisfy its equality. This applies to both zero coordinates and tight odd cuts. Consequently F_x=\operatorname{conv}\{a(M):M\in\mathcal M_x\}.

Discard the coordinates outside A and set

All diagonal entries of D are positive. By Lemma 2.3, x is relatively interior to F_x. Therefore

identifies a relative neighborhood of x in the face with a neighborhood of zero in the d-dimensional Euclidean space \mathcal T. Define

Their convex hull contains a neighborhood of zero in \mathcal T. All gradients, Hessians, operator inverses, and operator traces in the remainder of the proof are taken on \mathcal T. Coordinates with x_e=1 have not been discarded: their centered entries and all tangent directions are zero, so they cause no singularity on this space.

B.2 A finite exponential family on the normalized tangent space

We now express the face law of Lemma 3.2 in the normalized coordinates. Let p be the positive maximizing law at x, and write its parameter as \theta\in\mathbb R^A, restricting to supported coordinates. Since a(M)=x+D^{1/2}b_M,

Every b_M lies in \mathcal T. Thus only the orthogonal projection \lambda=\operatorname{proj}_{\mathcal T} (D^{1/2}\theta) affects the normalized law. Define

The law and its normalized mean then satisfy

The last equality is the zero mean of b_M under p. The parameter is finite because the original law is taken on its minimal face.

For any \eta\in\mathcal T, put

This law has exponential parameter D^{-1/2}\eta in the original coordinates, since the centering term is constant across atoms. Lemma 3.2 therefore shows that it maximizes entropy at its own mean y(\eta) and remains on the same minimal face. Differentiating the finite sum defining \Phi yields

Each C(\eta) is positive definite on \mathcal T. Indeed, zero variance in a direction u\in\mathcal T would make u\cdot b_M constant on all face atoms because p_\eta is positive. The affine span of the b_M is \mathcal T, so this forces u=0. Write C=C(\lambda).

B.3 The second variation and its trace

We have a positive definite covariance on a space of dimension d>s/2. We now compare its inverse with the marginal-entropy Hessian. This comparison uses the smooth exponential parameter; it does not require differentiability of H across faces.

Set

These functions are smooth near zero on \mathcal T. In the retained coordinates, the Hessian of F at x is -D^{-1}. The change of coordinates in Equation (72) therefore gives

By Equation (74), the smooth function

has a local maximum at \lambda. Its gradient is

Since C is invertible and z(\lambda)=0, stationarity implies \nabla L(0)+\lambda=0. Differentiating once more at \lambda, the derivative of C(\eta) is multiplied by this zero vector. Thus the second-derivative test gives

Congruence by C^{-1}, as an operator on \mathcal T, yields

Under p=p_\lambda, the normalized vector b_M has mean zero. For each edge e, its indicator in the random matching has variance x_e(1-x_e), so

The trace on \mathcal T equals the ambient trace because all the vectors b_M lie in \mathcal T. For u>0, the inequality u^{-1}\ge2-u follows from (u-1)^2/u\ge0. Applying it to the d positive eigenvalues of C gives

The last inequality is again the supported-face codimension bound.

It remains to include the nonlinear correction. Writing g=\nabla\widehat F(0), the full chain rule is

In particular, the rank-one term has trace f''(t)\|g\|_2^2/m\le0. Since t\le\ln(s/m), we also have f'(t)=8e^{-t}\ge8m/s. Combining Equations (71), (78), and (79), we obtain

This contradicts the negative semidefiniteness in Equation (76). Hence \Psi(y)\le0 throughout P, proving Theorem B.1.□

Proof. First count the distinct vertices occurring in a positive ordinary pair or having a positive loop count. If any of the n vertices is missing, it cannot be covered, so return zero. This test uses only the listed records, without enumerating the vertex set. Otherwise, if there are r positive pair records and s positive loop records, then n\le2r+s. Thus the constructions indexed by vertices below have size polynomial in the input length, even for a compact binary vertex count.

For each j\in\{0,\ldots,n\}, construct an ordinary loopless graph G_j by adjoining j labeled new vertices. Keep all original edges between distinct vertices. There are no edges among the new vertices, and the pair joining original vertex i to any new vertex has multiplicity \ell_i. Label these parallel edges by the corresponding original loop choices.

Every perfect matching of G_j pairs the new vertices to j distinct original vertices. Replace those pairs by their labeled loop choices and retain the other edges; this gives a matching counted by N_j. Conversely, each matching counted by N_j has exactly j! lifts, one for each bijection from the new vertices to its j loop-covered vertices. Edge labels preserve the loop choices independently of this bijection. Thus, including j=0,

Run the ordinary algorithm on each G_j, obtaining a nonnegative integer A_j, and return

Parity is tested on each transformed order n+j, as part of that ordinary algorithm. There is no initial rejection for odd n: a single vertex with a loop is already a positive-count example. The parity of n+j equals that of the number n-j of original vertices that remain to be paired by ordinary edges.

By Theorem 1.2 and Equation (81),

Since n+j\le2n, summing these inequalities proves the claimed factor 512^{2n}=2^{18n}. All terms are nonnegative, and A_j=0 exactly when N_j=0, so zero recognition is also exact.

The construction retains compressed multiplicity records: G_j has at most r+js positive pair records. No parallel-edge list is expanded. Each transformed graph has at most 2n vertices and uses only multiplicities already present in the input. If b_{\max} is the largest binary exponent of any positive pair or loop multiplicity, taking b_{\max}=0 when all multiplicities are zero, Proposition 10.1 bounds each call and gives O(n^2+nb_{\max}+1) bits for A_j. There are only n+1 calls. The rational sum can be represented exactly with the common denominator n!:

The denominator has O(n\log_2(n+1)+1) bits, and the numerator has O(n^2+nb_{\max}+n\log_2(n+1)+1) bits. Factorials, exact integer divisions, products, and the sum therefore take polynomial bit time. The case n=0 uses the single term j=0, with 0!=1 and A_0=1, so the empty matching is counted exactly.□