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 3 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 5 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 4 gives \(x_i\in P(G_i)\), and every retained coordinate is positive. Put \[n_i=|V(G_i)|,\qquad s_i=|E(G_i)|,\qquad d_i=\dim T(x_i).\] Each crossing label appears in both graphs, whereas each internal label appears in one. Consequently \[ n_1+n_2=n+2,\qquad s_1+s_2=|E|+|C|,\qquad 4\le n_i<n. \tag{9}\]

Consider the space of compatible directions \[W=\{(h_1,h_2)\in T(x_1)\oplus T(x_2): (h_1)_e=(h_2)_e\text{ for }e\in C\}.\] 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 \[\{z\in\mathbb R^C:\textstyle\sum_{e\in C}z_e=0\}.\] Since \(x(C)=1\), the set \(C\) is nonempty and this target has dimension \(|C|-1\). Its kernel is \(W\), whence \[\dim W\ge d_1+d_2-|C|+1.\]

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 3 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 \[\begin{align*} |E|-d(x) &\le (s_1-d_1)+(s_2-d_2)-1\\ &\le (3n_1/2-2)+(3n_2/2-2)-1 =3n/2-2. \end{align*}\] 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 5, 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 6 applied to \(G_f\) gives \[d(x)=\dim F_{\bar x}\ge |E_f(x)|-3m_f+2.\] 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=\mathop{\mathrm{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 \[\mathop{\mathrm{Ent}}((1-u)p+uq)-\mathop{\mathrm{Ent}}(p) =u\log(1/u)\sum_{a\in Z}q_a+O(u)>0\] 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 \[\mathop{\mathrm{Ent}}(q')\le\log\sum_{a\in\mathcal A_x}e^{\eta\cdot a}-\eta\cdot y,\] with equality for the exponential law itself. This proves maximality. ◻

Proof. Let \(p\) and \(\theta\) be supplied by Lemma 9, and write \(T=\operatorname{span}(F_x-x)\). For \(v\in\mathbb R^E\) and real \(t\), set \[\Phi(t)=\log\sum_{a\in\mathcal A_x}e^{(\theta+tv)\cdot a},\qquad p_a(t)=e^{(\theta+tv)\cdot a-\Phi(t)},\qquad y(t)=\sum_a p_a(t)a.\] The lemma gives \(F_{y(t)}=F_x\) and \[ H(y(t))=\Phi(t)-(\theta+tv)\cdot y(t). \tag{16}\] 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 \[K=\sum_{a\in\mathcal A_x}p_a(a-x)(a-x)^{\mathsf T}.\] 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 \[ \ker K=T^\perp,\qquad \operatorname{im}K=T, \qquad \mathop{\mathrm{rank}}K=d. \tag{17}\] 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: \[g_e=-\log x_e-c\log(1-x_e)-(c+1),\qquad D_{ee}=-\frac1{x_e}+\frac{c}{1-x_e}.\] 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 \[\begin{aligned} r'(0)&=(g+\theta)\cdot Kv,\\ r''(0)&=(Kv)^{\mathsf T}D(Kv)+v^{\mathsf T}Kv +(g+\theta)\cdot y''(0). \end{aligned}\] 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 \[ 0\ge (Kv)^{\mathsf T}D(Kv)+v^{\mathsf T}Kv \qquad(v\in\mathbb R^E). \tag{18}\] 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 \[0\ge d+\sum_i\lambda_i u_i^{\mathsf T}Du_i =d+\mathop{\mathrm{tr}}(KD).\] 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 \[\mathop{\mathrm{tr}}(KD)=\sum_e\bigl[-(1-x_e)+cx_e\bigr]=-s+(c+1)m,\] which proves Equation (15). ◻

Lower bound in Theorem 1. Write the original vertex count as \(2M\ge2\), and fix \(c=2-2/M+\varepsilon\) with \(\varepsilon>0\). By Lemma 8, \(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 7 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 10 gives \[0\ge d-s+(c+1)m\ge 2+(c-2)m =2\left(1-\frac mM\right)+\varepsilon m>0.\] 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. 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 \[\mathop{\mathrm{Ent}}(X_{\delta(v)}) =\sum_{e\in\delta(v)} \mathop{\mathrm{Ent}}\bigl(X_e\mid X_f:f\in\delta(v),\ f<e\bigr) \ge\sum_{e\in\delta(v)}\mathop{\mathrm{Ent}}\bigl(X_e\mid X_f:f<e\bigr).\] 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\mathop{\mathrm{Ent}}(X_{\delta(v)})\ge2\mathop{\mathrm{Ent}}(X)\). At a vertex the star vector makes exactly one choice, with probabilities \((x_e)_{e\in\delta(v)}\), so \[\mathop{\mathrm{Ent}}(X)\le\frac12\sum_v\left[-\sum_{e\in\delta(v)}x_e\log x_e\right] =F(x).\] 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 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 12 gives \(F(x)\le H(x)+2m-2\le\ln N+2m-2\) at every \(x\in P\). Also, \[H_{\mathrm{bin}}(x)-H(x) \le\left(3-\frac2m\right)B(x)\le3m-2.\] 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 \[x=\frac1k\sum_{i=1}^k\mathbf1_{M_i}\in P(G)\] 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 \[B(x)=-m(k-1)\ln(1-1/k).\] Since \(H(x)\le\ln N(G)\), Theorem 1 now gives \[\ln N(G)\ge m\ln k+2(m-1)(k-1)\ln(1-1/k).\] 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 4 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 \[k|S|=2|E(S)|+|\delta(S)|.\] 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 16 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 \[c\ge \frac{(m-1)\ln3}{2m\ln(3/2)}.\] Let \(m\) tend to infinity. The graphs with \(m\ge2\) are simple, so the same limit applies under that restriction. ◻

Proof. For each pair with \(k_e>0\), put \(r_e=2^{\lfloor\log_2 k_e\rfloor}\). Then \[\frac{k_e}{2}\le r_e\le k_e.\] 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 \[ 2^{-n/2}N\le Z_{\mathrm{good}}\le N. \tag{33}\] 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 \[Z_{\mathrm{bad}}\le 2^{p+b_{\max}n/2-L}\le2^{-20n}.\] For the last inequality, put \(t=n+b_{\max}+1\ge5\) and note that \[p+\frac{b_{\max}n}{2}+20n\le t^2+20t\le100t^3=L.\] 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 \[Z_\beta\le N+2^{-20n}\le2N\] 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 \[\psi(t)-kt=2^{-k}-t\ge0, \qquad \phi(t)\le(k+1)t.\] 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 \[\phi(t)-\psi(t)=2^{-K}(-r\log_2 r)\le2^{-K}.\] 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 \[\sum_{e:x_e\ge2^{-K}}x_e +\bigl|\{e:x_e<2^{-K}\}\bigr|\,2^{-K} \le \frac n2+p2^{-K} \le \frac n2+1 \le n.\] This proves Equation (35). ◻

Proof. First let \(A,B\in\mathcal S_x\) cross, and put \[I=A\cap B,\qquad D=A\setminus B,\qquad D'=B\setminus A,\qquad O=V\setminus(A\cup B).\] 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 \[ \chi_A+\chi_B= \chi_I+\chi_{A\cup B}+2\mathbf1_{E(D,D')}. \tag{53}\] 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 \[ \chi_A+\chi_B= \chi_D+\chi_{D'}+2\mathbf1_{E(I,O)}. \tag{54}\] 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 \[ \chi_A+\chi_B=\chi_U+\chi_W. \tag{55}\]

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 6. Take the laminar spanning family from Lemma 29. 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 \[2m-1 =\sum_{S\text{ internal}} \bigl(\#\text{children of }S-1\bigr) \ge(c-1)+2q.\] 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 4. 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 \[ \mathcal Q:\mathbb R^A\longrightarrow (\mathbb R^{A_1}/U_1)\oplus(\mathbb R^{A_2}/U_2),\qquad \mathcal Q(u)=(r_1(u)+U_1,r_2(u)+U_2). \tag{57}\] 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 3 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 \[\ell_i:\mathbb R^{A_i}/U_i\longrightarrow\mathbb R, \qquad \ell_i(z+U_i)=\sum_{e\in C}z_e\] 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\), \[\ell_1(r_1(u)+U_1)=\sum_{e\in C}u_e =\ell_2(r_2(u)+U_2).\] 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 \[\begin{align*} s_A-d(x)&=\operatorname{codim}U_x \le\operatorname{codim}\ker\mathcal Q=\operatorname{rank}\mathcal Q\\ &\le\operatorname{codim}U_1+\operatorname{codim}U_2-1\\ &\le(3n_1/2-2)+(3n_2/2-2)-1=3n/2-2. \end{align*}\] 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 30 now gives \[d(x)\ge \dim T(\bar x) \ge |E_f(x)|-2(s_f-2).\] 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 8 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 9. For any \(v\in\mathbb R^E\) and \(t\in\mathbb R\), define \[p_a(t)= \frac{\exp((\theta+tv)\cdot a)} {\sum_{b\in\mathcal A_x}\exp((\theta+tv)\cdot b)}, \qquad x(t)=\sum_{a\in\mathcal A_x}p_a(t)a.\] The same lemma shows that \(x(t)\) stays in the relative interior of \(F_x\) and \[ H(x(t)) =\Phi(t)-(\theta+tv)\cdot x(t), \qquad \Phi(t)=\ln\sum_{a\in\mathcal A_x} \exp((\theta+tv)\cdot a). \tag{60}\] Thus we may differentiate along these curves without assuming differentiability of \(H\) across faces.

Let \[C=\sum_{a\in\mathcal A_x}p_a(a-x)(a-x)^{\mathsf T}\] 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\), \[w^{\mathsf T}Cw =\sum_{a\in\mathcal A_x}p_a\bigl(w\cdot(a-x)\bigr)^2.\] All \(p_a\) are positive, and \(\operatorname{span}\{a-x:a\in\mathcal A_x\}=T(x)\). Since \(C\) is symmetric, it follows that \[ \ker C=T(x)^\perp,\qquad \operatorname{im}C=T(x),\qquad \operatorname{rank}C=d(x). \tag{61}\] 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 \[g_e=-\ln x_e-c\ln(1-x_e)-(c+1), \qquad D_{ee}=-\frac1{x_e}+\frac c{1-x_e};\] 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 \[\frac{d}{dt} H(x(t)) =-(\theta+tv)\cdot x'(t).\] Both signs of \(t\) are permitted. The minimum property at \(t=0\) therefore gives \[(\theta+g)\cdot Cv=0 \qquad\text{for every }v\in\mathbb R^E.\] 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 \[ \begin{aligned} 0 &\le \left.\frac{d^2}{dt^2} \bigl( H(x(t))-J_c(x(t))\bigr)\right|_{t=0}\\ &=-v^{\mathsf T}Cv-(\theta+g)\cdot x''(0) -(Cv)^{\mathsf T}D(Cv)\\ &=-v^{\mathsf T}Cv-(Cv)^{\mathsf T}D(Cv). \end{aligned} \tag{62}\]

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 \[ d(x)\le \sum_{i=1}^d\lambda_i u_i^{\mathsf T}(-D)u_i =\operatorname{tr}(C(-D)). \tag{63}\] 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 31 gives \[ \begin{aligned} \operatorname{tr}(C(-D)) &=\sum_{e\in E_f(x)}x_e(1-x_e) \left(\frac1{x_e}-\frac c{1-x_e}\right)\\ &=|E_f(x)|-(c+1)\sum_{e\in E_f(x)}x_e =|E_f(x)|-\frac{c+1}{2}s_f. \end{aligned} \tag{64}\] For \(c=4\), the weaker consequence \(d(x)\ge|E_f(x)|-2s_f\) of the residual dimension bound suffices: \[\operatorname{tr}(C(-D))=|E_f(x)|-\tfrac52s_f <|E_f(x)|-2s_f\le d(x),\] 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 \[d(x)\ge|E_f(x)|-2(s_f-2) =|E_f(x)|-2s_f+4 >\operatorname{tr}(C(-D)).\] If \(s_f=2\), then \[d(x)\ge|E_f(x)|-1>|E_f(x)|-4 =\operatorname{tr}(C(-D)).\] 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 32 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 36.

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 13. The sharper error \(3m-2\) in that corollary improves both comparisons on the same domain. ◻

Proof. For the selected matching mixture in Theorem 14, \(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 33, then exponentiating, gives the first bound. The inequality \((k-1)\ln(1-1/k)\ge-1\) from the proof of Theorem 14 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 15 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 34; 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 36. Define \[f(t)=8(1-e^{-t}), \qquad \Psi(y)=F(y)-H(y)-mf\bigl(F(y)/m\bigr).\] Suppose that \(\Psi\) is positive somewhere. By Lemma 8, it has a positive maximum at some \(x\in P\). Let \(F_x\) be the minimal face containing \(x\), and put \[A=\{e\in E:x_e>0\},\qquad s=|A|,\qquad d=\dim F_x,\qquad t=F(x)/m.\] 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 \[0\le t\le\ln(s/m).\] 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 30 now yields \[ d\ge s-4m>\frac{s}{2}>0. \tag{71}\] Thus all integral and low-entropy cases have already been excluded before any covariance inverse is introduced.

Let \[\mathcal M_x=\{M\in\mathcal M:a(M)\in F_x\}.\] 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 \[ D=\operatorname{diag}(x_e:e\in A),\qquad \mathcal T=D^{-1/2}T(x) =\operatorname{span}\bigl(D^{-1/2}(F_x-x)\bigr) \subseteq\mathbb R^A. \tag{72}\] All diagonal entries of \(D\) are positive. By Lemma 5, \(x\) is relatively interior to \(F_x\). Therefore \[z=D^{-1/2}(y-x),\qquad y=x+D^{1/2}z\] identifies a relative neighborhood of \(x\) in the face with a neighborhood of zero in the \(d\)-dimensional Euclidean space \(\mathcal T\). Define \[b_M=D^{-1/2}(a(M)-x),\qquad M\in\mathcal M_x.\] 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.