betaFeedback

WorksMathematics

Sharp lower bounds for weighted bisections of graphs with bounded maximum degree

Abstract

A bisection of a graph is a partition of its vertex set into two parts the sizes of which differ by at most one. We prove that every finite simple graph of maximum degree at most an odd positive integer kk, with arbitrary nonnegative real edge weights, has a bisection of weight at least (k+1)/(2k)(k+1)/(2k) times its total edge weight. The corresponding bound (k+2)/(2(k+1))(k+2)/(2(k+1)) for even kk follows immediately. Both coefficients are best possible. Somewhat surprisingly, these are exactly the sharp coefficients known for maximum weighted cuts, despite the additional balance requirement.

Introduction

All graphs considered in this paper are finite and simple, except for multigraphs obtained explicitly by contraction. Let G=(V,E)G=(V,E) be a graph with an edge-weight function w:E→R≥0w:E\to\mathbb{R}_{\ge0}. Write w(G)=∑e∈Ew(e)w(G)=\sum_{e\in E}w(e). A cut is the set of edges joining the two parts of a partition of VV. A cut is a bisection if the part sizes differ by at most one. Let bis⁡w(G)\operatorname{bis}_{w}(G) denote the maximum weight of a bisection of GG, and let cut⁡w(G)\operatorname{cut}_{w}(G) denote the maximum weight of an unrestricted cut. Thus bis⁡w(G)≤cut⁡w(G)\operatorname{bis}_{w}(G)\le\operatorname{cut}_{w}(G).

The maximum-cut problem and the maximum-bisection problem both seek a partition with large crossing weight. The balance requirement makes the latter more restrictive. Pairing the vertices arbitrarily, leaving at most one vertex unpaired, and assigning the vertices in each pair to opposite sets independently and uniformly gives the elementary bound bis⁡w(G)≥w(G)/2\operatorname{bis}_{w}(G)\ge w(G)/2. A natural question is how much the maximum-degree bound improves this estimate.

Classical results on cuts in graphs with chromatic number χ\chi [1, 7, 8] give a cut with at least a proportion

pχ={χ+12χ,χ odd,χ2(χ−1),χ evenp_{\chi} = \begin{cases} \dfrac{\chi+1}{2\chi}, & \chi\text{ odd},\\[4pt] \dfrac{\chi}{2(\chi-1)}, & \chi\text{ even} \end{cases}

of all edges, for χ≥2\chi\ge2. The same argument gives cut⁡w(G)≥pχw(G)\operatorname{cut}_{w}(G)\ge p_{\chi}w(G) for arbitrary nonnegative edge weights. Indeed, fix a proper χ\chi-coloring and choose uniformly a set of ⌊χ/2⌋\lfloor\chi/2\rfloor colors for one part, placing the remaining colors in the other part. Every edge joins distinct colors and is separated with probability

2⌊χ/2⌋⌈χ/2⌉χ(χ−1)=pχ.\frac{2\lfloor\chi/2\rfloor\lceil\chi/2\rceil}{\chi(\chi-1)}=p_{\chi}.

Linearity of expectation proves the weighted bound. If GG has no edges, the corresponding weighted statements are immediate.

In particular, a proper (k+1)(k+1)-coloring of a graph with maximum degree at most kk yields

cut⁡w(G)≥ckw(G),ck={k+12k,k odd,k+22(k+1),k even.(1)\operatorname{cut}_{w}(G)\ge c_{k}w(G),\qquad c_{k}= \begin{cases} \frac{k+1}{2k}, & k\text{ odd},\\ \frac{k+2}{2(k+1)}, & k\text{ even}. \end{cases} \tag*{(1)}

These coefficients are sharp for complete graphs with unit weights. However, balancing the numbers of colors does not balance the numbers of vertices: color classes can have very different sizes. Thus this argument may not give a bisection, so cannot be used to give the same guarantee for bisections.

The distinction can be substantial even for simple weighted graphs. For the star K1,2r−1K_{1,2r-1} with unit weights, the maximum cut contains all 2r−12r-1 edges, whereas every bisection has at most rr crossing edges. In general, therefore, requiring balance can reduce the optimum to close to half the maximum-cut value. Therefore, it is somewhat surprising that the sharp universal maximum-degree bounds (1), first obtained for unrestricted cuts, continue to hold for maximum weighted bisections.

The unweighted case was recently resolved by Guo and Gutin [5] improving on a bound by Lee, Loh and Sudakov [6] and a result by Bollobás and Scott [2] who had established the exact bound (k+1)m/(2k)(k+1)m/(2k) for kk-regular graphs when kk is odd. Their proof cannot be extended to the weighted case.

Our main result resolves this case.

Theorem 1.1. Let kk be an odd positive integer. Every graph GG with Δ(G)≤k\Delta(G)\le k and nonnegative real edge weights satisfies

bis⁡w(G)≥k+12kw(G).\operatorname{bis}_{w}(G)\ge\frac{k+1}{2k}w(G).

Applying Theorem 1.1 with k+1k+1 instead of kk gives the following previously known even-degree bound as an immediate consequence.

Corollary 1.2. Let kk be a positive even integer. Every graph GG with Δ(G)≤k\Delta(G)\le k and nonnegative real edge weights satisfies

bis⁡w(G)≥k+22(k+1)w(G).\operatorname{bis}_{w}(G)\ge\frac{k+2}{2(k+1)}w(G).

Together these statements establish [4 Conjecture 1.1] in full: the balance requirement causes no loss in the sharp universal weighted-cut coefficients ckc_k. Both coefficients are best possible: with unit weights, w(Kk+1)=k(k+1)/2w(K_{k+1})=k(k+1)/2 and every bisection of Kk+1K_{k+1} has weight ⌊(k+1)2/4⌋\lfloor(k+1)^2/4\rfloor, so

bis⁡w(Kk+1)w(Kk+1)=ck.\frac{\operatorname{bis}_{w}(K_{k+1})}{w(K_{k+1})}=c_k.

Neither connectedness nor a positive minimum degree is assumed.

Our proof uses a lower bound based on matchings and in particular Edmonds’ characterisation of the matching polytope and its dual. This allows us to establish a probability space and the use of the probabilistic method.

Matching preliminaries

For a graph or multigraph HH, write e(H)=∣E(H)∣e(H)=|E(H)|, counting parallel edges separately. For disjoint vertex sets X,YX,Y, let eH(X,Y)e_H(X,Y) be the number of edges joining them. A matching is perfect if it covers every vertex, and near-perfect if it leaves exactly one vertex uncovered. That vertex is called exposed. A nonempty graph HH is factor-critical if H−vH-v has a perfect matching for every v∈V(H)v\in V(H). A family of sets is laminar if any two of its members are disjoint or one contains the other.

For the rest of the proof, kk is a fixed odd positive integer. For every odd vertex set TT in a graph HH, let the excess of TT be defined as follows

ex⁡kH(T)=e(H[T])−k(∣T∣−1)2.\operatorname{ex}^{H}_{k}(T)=e(H[T])-\frac{k(|T|-1)}{2}.

We call TT overfull if ex⁡kH(T)>0\operatorname{ex}^{H}_{k}(T)>0, and omit the superscript when the ambient graph is clear. We use Tutte’s theorem [9]: a graph has a perfect matching if and only if deleting any vertex set AA leaves at most ∣A∣|A| odd components.

Note that if MM is a matching in HH then the incidence vector of MM is (xe:e∈E(H))(x_e:e\in E(H)) with xe=1x_e=1 if e∈Me\in M and xe=0x_e=0, otherwise. The first two conditions in Theorem 2.1 describe all matchings of HH provided all xex_e are integral. The third condition is needed in order to get the convex hull when we allow all xex_e to be real.

Theorem 2.1 (Edmonds [3]). For a loopless multigraph HH, the convex hull of the incidence vectors of its matchings is described by

xe≥0,∑e∋vxe≤1(v∈V(H)),∑e∈E(H[T])xe≤∣T∣−12(∣T∣ odd).(2)x_e\ge0,\qquad\sum_{e\ni v}x_e\le1\quad(v\in V(H)),\qquad\sum_{e\in E(H[T])}x_e\le\frac{|T|-1}{2}\quad(|T|\text{ odd}). \tag*{(2)}

Corollary 2.2. Let HH be a loopless multigraph with maximum degree at most kk and no overfull odd set. For every real edge weighting, HH has a matching of weight at least w(H)/kw(H)/k.

Proof. The vector x=(xe:e∈E(H))x=(x_e:e\in E(H)) with xe=1/kx_e=1/k satisfies (2). Its weighted objective is w(H)/kw(H)/k, and some matching has at least this weight by Theorem 2.1. □

Corollary 2.3. Let kk be an odd integer, let GG be a simple graph with maximum degree at most kk, and suppose that GG has no overfull odd set. Then, for every nonnegative edge weighting,

bisw⁡(G)≥k+12kw(G).\operatorname{bisw}(G)\ge\frac{k+1}{2k}w(G).

Proof. By Corollary 2.2, there is a matching MM with w(M)≥w(G)/kw(M)\ge w(G)/k. The matching-to-bisection bound of Gerke, Gutin, Yeo and Zhou [4 Corollary 2.3] gives

bisw⁡(G)≥w(G)+w(M)2≥k+12kw(G).\operatorname{bisw}(G)\ge\frac{w(G)+w(M)}{2}\ge\frac{k+1}{2k}w(G).

For completeness, the first inequality follows by pairing the endpoints of each edge of MM, pairing the remaining vertices arbitrarily (leaving at most one unpaired), and assigning the vertices in each pair to opposite sets independently and uniformly. Every matching edge is in the cut, and every other edge is in the cut with probability at least 1/21/2. □

Consequently, any counterexample to Theorem 1.1 must contain an overfull odd set. The remaining arguments control the cost of expanding such sets after contraction.

Lemma 2.4. Let HH be a factor-critical graph of odd order h≥3h \ge3, with real edge weights wHw_H. Suppose that, for every vertex vv, the maximum weight of a perfect matching of H−vH-v is the same number cc. Then, there exist a laminar family L\mathcal{L} of proper odd vertex sets, positive numbers zTz_T for T∈LT \in\mathcal{L}, a real number λ\lambda, and nonnegative slacks ses_e, such that

wH(e)=λ+∑T∈Le∈E(H[T])zT−se,(3)w_H(e) = \lambda+ \sum_{\substack{T \in\mathcal{L}\\e\in E(H[T])}} z_T - s_e, \tag*{(3)}

and

c=h−12λ+∑T∈L∣T∣−12zT.(4)c = \frac{h-1}{2}\lambda+ \sum_{T \in\mathcal{L}} \frac{|T|-1}{2}z_T. \tag*{(4)}

Moreover, every near-perfect matching of weight cc contains exactly (∣T∣−1)/2(|T|-1)/2 edges of H[T]H[T] for each T∈LT \in\mathcal{L}.

Proof. Choose C>∑e∈E(H)∣wH(e)∣C > \sum_{e \in E(H)} |w_H(e)| and replace the edge weight of each edge ee by

w‾H(e):=wH(e)+C.\overline{w}_H(e) := w_H(e) + C.

For any two matchings M,NM,N, we have ∣wH(M)−wH(N)∣≤∑e∈E(H)∣wH(e)∣<C|w_H(M)-w_H(N)| \le\sum_{e \in E(H)} |w_H(e)| < C. Thus, under the new weights, a matching with more edges always has larger weight. In particular, every maximum-weight matching now has (h−1)/2(h-1)/2 edges. By Theorem 2.1, the maximum-weight matching problem is equivalent to the following linear program:

(P)max⁡∑e∈E(H)w‾H(e)⋅xes.t.∑e∋vxe≤1,for all v∈V(H),∑e∈EH(T)xe≤∣T∣−12,for all T⊆V(H), ∣T∣ odd,xe≥0,for all e∈E(H).\begin{aligned} \text{(P)}\quad\max\quad&\sum_{e \in E(H)} \overline{w}_H(e)\cdot x_e\\ \text{s.t.}\quad&\sum_{e \ni v}x_e \le1,\qquad&&\text{for all }v \in V(H),\\ &\sum_{e \in E_H(T)}x_e \le\frac{|T|-1}{2},\qquad&&\text{for all }T \subseteq V(H),\ |T|\text{ odd},\\ &x_e \ge0,\qquad&&\text{for all }e \in E(H). \end{aligned}

Thus, its dual is

(D)min⁡∑v∈V(H)yv+∑T⊆V(H)∣T∣ odd∣T∣−12zTs.t.yu+yv+∑T⊆V(H)∣T∣ odduv∈EH(T)zT≥w‾H(uv),for all uv∈E(H),yv≥0,for all v∈V(H),zT≥0,for all T⊆V(H), ∣T∣ odd.(5)\begin{aligned} \text{(D)}\quad\min\quad&\sum_{v \in V(H)}y_v+\sum_{\substack{T \subseteq V(H)\\|T|\text{ odd}}}\frac{|T|-1}{2}z_T\\ \text{s.t.}\quad&y_u+y_v+\sum_{\substack{T \subseteq V(H)\\|T|\text{ odd}\\uv\in E_H(T)}}z_T \ge\overline{w}_H(uv),\qquad&&\text{for all }uv \in E(H),\\ &y_v \ge0,\qquad&&\text{for all }v \in V(H),\\ &z_T \ge0,\qquad&&\text{for all }T \subseteq V(H),\ |T|\text{ odd}. \tag*{(5)} \end{aligned}

Here yvy_v and zTz_T are the dual variables corresponding to the vertex constraints and the odd-set constraints, respectively.

For every u∈V(H)u \in V(H), let MuM_u be a maximum-weight perfect matching of H−uH-u, and let xu∈R∣E(H)∣x_u \in\mathbb{R}^{|E(H)|} denote its characteristic vector, i.e., xu(e)=1x_u(e)=1 if e∈Mue \in M_u and 00 otherwise. By our assumption, all these matchings have the same original weight cc, and hence their characteristic vectors are optimal solutions of (P). Since every xux_u is optimal for (P), their average x∗=h−1∑u∈V(H)xux^* = h^{-1}\sum_{u \in V(H)}x_u is optimal for (P). Moreover, for every v∈V(H)v \in V(H), we have

∑e∋vxe∗=1h∑u∈V(H)∑e∋vxu(e)=h−1h<1,\sum_{e \ni v}x_e^*=\frac{1}{h}\sum_{u \in V(H)}\sum_{e \ni v}x_u(e)=\frac{h-1}{h}<1,

where the last equality holds since MuM_u contains exactly one edge incident with vv when u≠vu \ne v, while MvM_v contains none. Thus, the complementary slackness theorem implies that every optimal solution of (D) satisfies

yv=0 for all v∈V(H).(6)y_v = 0 \text{ for all } v \in V(H). \tag*{(6)}

Among all optimal solutions of (D), choose one minimizing the potential

Φ=∑T⊆V(H)∣T∣ odd∣T∣(h−∣T∣)zT.\Phi= \sum_{\substack{T \subseteq V(H)\\ |T|\ \mathrm{odd}}} |T|(h-|T|)z_T.

Such a choice is possible since the optimal dual solutions form a nonempty polyhedron and Φ≥0\Phi\ge0. Let L′={T⊆V(H):∣T∣ odd, zT>0}\mathcal{L}' = \{T \subseteq V(H) : |T| \text{ odd},\ z_T > 0\}.

Claim 2.5. L′\mathcal{L}' is a laminar family.

Proof. Suppose, for a contradiction, that there are two crossing sets A,B∈L′A,B \in\mathcal{L}', i.e., A∩BA \cap B, A∖BA \setminus B and B∖AB \setminus A are all nonempty. Let I=A∩BI = A \cap B and α=min⁡{zA,zB}>0\alpha= \min\{z_A,z_B\} > 0.

First suppose that ∣I∣|I| is even. Since AA and BB are odd, both A∖BA \setminus B and B∖AB \setminus A are odd. We decrease zA,zBz_A,z_B by α\alpha, increase zA∖B,zB∖Az_{A\setminus B},z_{B\setminus A} by α\alpha, and increase yvy_v by α\alpha for every v∈Iv \in I. We claim that every dual constraint remains satisfied. Indeed, for any edge e=uve=uv, if both endpoints are in II, then the decrease of zAz_A and zBz_B is compensated by the increase of yuy_u and yvy_v. If both endpoints are in A∖BA \setminus B or both are in B∖AB \setminus A, then the decrease of zAz_A or zBz_B is compensated by the increase of zA∖Bz_{A\setminus B} or zB∖Az_{B\setminus A}, respectively. If one endpoint is in II and the other is in A∖BA \setminus B or B∖AB \setminus A, then the decrease of zAz_A or zBz_B is compensated by the increase of the vertex variable at the endpoint in II. For all other edges, the left-hand side of the dual constraint does not decrease. Moreover, the dual objective remains unchanged, since

∣I∣+∣A∖B∣−12+∣B∖A∣−12=∣A∣−12+∣B∣−12.|I|+\frac{|A\setminus B|-1}{2}+\frac{|B\setminus A|-1}{2}=\frac{|A|-1}{2}+\frac{|B|-1}{2}.

Thus, we obtain another optimal solution of (D) with yv>0y_v > 0 for every v∈Iv \in I, contradicting (6).

Now suppose that ∣I∣|I| is odd. Then both II and A∪BA \cup B are odd. We decrease zA,zBz_A,z_B by α\alpha and increase zI,zA∪Bz_I,z_{A\cup B} by α\alpha. Again, we claim that every dual constraint remains satisfied. Indeed, for any edge ee, if both endpoints are in II, then the decrease of zA,zBz_A,z_B is compensated by the increase of zI,zA∪Bz_I,z_{A\cup B}. If both endpoints are in A∖BA \setminus B or both are in B∖AB \setminus A, or if one endpoint is in II and the other is in A∖BA \setminus B or B∖AB \setminus A, then the decrease of zAz_A or zBz_B is compensated by the increase of zA∪Bz_{A\cup B}. If one endpoint is in A∖BA \setminus B and the other is in B∖AB \setminus A, then the left-hand side of the dual constraint increases by α\alpha (due to zA∪Bz_{A\cup B}). For all remaining edges, it remains unchanged. Moreover, the dual objective remains unchanged as ∣A∣+∣B∣=∣I∣+∣A∪B∣|A|+|B|=|I|+|A\cup B|. However, the potential Φ\Phi decreases by

α(∣A∣(h−∣A∣)+∣B∣(h−∣B∣)−∣I∣(h−∣I∣)−∣A∪B∣(h−∣A∪B∣))=α(∣A∪B∣2+∣I∣2−∣A∣2−∣B∣2)=α((∣A∖B∣+∣B∖A∣+∣I∣)2+∣I∣2−(∣A∖B∣+∣I∣)2−(∣B∖A∣+∣I∣)2)=2α∣A∖B∣∣B∖A∣>0,\begin{aligned} &\alpha\bigl(|A|(h-|A|)+|B|(h-|B|)-|I|(h-|I|)-|A\cup B|(h-|A\cup B|)\bigr)\\ &=\alpha\bigl(|A\cup B|^2+|I|^2-|A|^2-|B|^2\bigr)\\ &=\alpha\bigl((|A\setminus B|+|B\setminus A|+|I|)^2+|I|^2-(|A\setminus B|+|I|)^2-(|B\setminus A|+|I|)^2\bigr)\\ &=2\alpha|A\setminus B||B\setminus A|>0, \end{aligned}

where the second equality follows from ∣A∣+∣B∣=∣I∣+∣A∪B∣|A|+|B|=|I|+|A\cup B|. This contradicts the minimality of Φ\Phi. Thus, no two sets in L′\mathcal{L}' cross, and hence L′\mathcal{L}' is laminar.

Let L=L′∖{V(H)}\mathcal{L}=\mathcal{L}'\setminus\{V(H)\} and λ=zV(H)−C\lambda=z_{V(H)}-C. Note that zV(H)=0z_{V(H)}=0 if V(H)∉L′V(H)\notin\mathcal{L}'. Thus, for every edge e∈E(H)e\in E(H), by (5), (6) and the definition of L′\mathcal{L}', we have

∑T∈L′e∈E(H[T])zT≥wH(e)+C.\sum_{\substack{T\in\mathcal{L}'\\e\in E(H[T])}} z_T \ge w_H(e)+C.

Let se≥0s_e\ge0 be the slack in this inequality. Then, by the definitions of L\mathcal{L}, λ\lambda and w^H\widehat{w}_H, we obtain (3).

On the other hand, by strong duality, the optimal value p∗p^* of (P) equals the optimal value q∗q^* of (D). Recall that every maximum-weight matching under the new weights w^H\widehat{w}_H is near-perfect, and the maximum original weight of a near-perfect matching is cc. Thus, p∗=c+h−12Cp^*=c+\frac{h-1}{2}C. In addition, by (6),

q∗=∑T⊆V(H)∣T∣ odd∣T∣−12⋅zT=∑T∈L′∣T∣−12⋅zT.q^*=\sum_{\substack{T\subseteq V(H)\\ |T|\ \mathrm{odd}}}\frac{|T|-1}{2}\cdot z_T =\sum_{T\in\mathcal{L}'}\frac{|T|-1}{2}\cdot z_T.

where the last equality follows from the definition of L′\mathcal{L}'. Thus,

c+h−12C=p∗=q∗=h−12zV(H)+∑T∈L∣T∣−12zT.c+\frac{h-1}{2}C=p^*=q^*=\frac{h-1}{2}z_{V(H)}+\sum_{T\in\mathcal{L}}\frac{|T|-1}{2}z_T.

Substituting λ=zV(H)−C\lambda=z_{V(H)}-C gives (4).

Finally, let MM be any near-perfect matching of weight cc. Then MM is optimal for (P) under the new weights. Since zT>0z_T>0 for every T∈LT\in\mathcal{L}, the complementary slackness theorem implies that the corresponding odd-set constraint is tight for MM, i.e.,

∣M∩E(H[T])∣=∣T∣−12,∀T∈L.|M\cap E(H[T])|=\frac{|T|-1}{2},\qquad\forall T\in\mathcal{L}.

This completes the proof.

An extremal packing of odd sets

In this section, we always assume that kk is a positive odd integer and G=(V(G),E(G),wG)G=(V(G),E(G),w_G) is a weighted graph with maximum degree at most kk. A family P\mathcal{P} of pairwise disjoint overfull odd vertex sets in GG is called an extremal packing if it maximizes ∑S∈Pex⁡k(S)\sum_{S\in\mathcal{P}}\operatorname{ex}_k(S) and, subject to this, minimizes ∑S∈P∣S∣\sum_{S\in\mathcal{P}}|S|. The empty family is allowed.

Note that every overfull odd set SS satisfies

∣S∣(∣S∣−1)2−k(∣S∣−1)2≥e(G[S])−k(∣S∣−1)2=ex⁡k(S)>0,\frac{|S|(|S|-1)}{2}-\frac{k(|S|-1)}{2}\ge e(G[S])-\frac{k(|S|-1)}{2}=\operatorname{ex}_k(S)>0,

and therefore ∣S∣>k|S|>k. Since both kk and ∣S∣|S| are odd, we have

∣S∣≥k+2.(7)|S|\ge k+2. \tag*{(7)}

Lemma 3.1. Let P\mathcal{P} be an extremal packing in GG. Then every G[S]G[S], S∈PS\in\mathcal{P}, is factor-critical. Moreover:

(i) for every S∈PS\in\mathcal{P} and every family of pairwise disjoint overfull odd subsets Tj⊆ST_j\subseteq S,

∑jex⁡k(Tj)≤ex⁡k(S);(8)\sum_j\operatorname{ex}_k(T_j)\le\operatorname{ex}_k(S); \tag*{(8)}

(ii) contracting all members of P\mathcal{P}, and retaining each original external edge separately, gives a loopless multigraph QQ with maximum degree at most kk and no overfull odd set.

Proof. Fix an arbitrary S∈PS \in\mathcal{P}. We first show that G[S]G[S] is factor-critical. Suppose, for a contradiction, that there exists a vertex r∈Sr \in S such that G[S]−rG[S]-r has no perfect matching. Then, by Tutte’s theorem, there is a subset B⊆S∖{r}B \subseteq S \setminus\{r\} such that G[S]−(B∪{r})G[S]-(B \cup\{r\}) has q>∣B∣q > |B| odd components C1,…,CqC_1,\ldots,C_q. Since ∣S∣−1|S|-1 is even, qq and ∣B∣|B| must have the same parity, and hence q≥∣B∣+2q \geq|B|+2. Let A=B∪{r}A=B \cup\{r\}. Then

q≥∣A∣+1.(9)q \geq|A|+1. \tag*{(9)}

Let RR be the union of all even components of G[S]−AG[S]-A. Thus,

ex⁡k(S)−∑i=1qex⁡k(Ci)=e(G[S])−∑i=1qe(G[Ci])−(k(∣S∣−1)2−∑i=1qk(∣Ci∣−1)2)=e(G[S])−∑i=1qe(G[Ci])−k(∣S∣−∑i=1q∣Ci∣+q−1)2=e(G[S])−∑i=1qe(G[Ci])−k(∣A∣+∣R∣+q−1)2≤e(G[S])−∑i=1qe(G[Ci])−k∣A∣−k∣R∣2≤0,\begin{aligned} \operatorname{ex}_k(S)-\sum_{i=1}^{q}\operatorname{ex}_k(C_i) &=e(G[S])-\sum_{i=1}^{q}e(G[C_i])-\left(\frac{k(|S|-1)}{2}-\sum_{i=1}^{q}\frac{k(|C_i|-1)}{2}\right)\\ &=e(G[S])-\sum_{i=1}^{q}e(G[C_i])-\frac{k\left(|S|-\sum_{i=1}^{q}|C_i|+q-1\right)}{2}\\ &=e(G[S])-\sum_{i=1}^{q}e(G[C_i])-\frac{k(|A|+|R|+q-1)}{2}\\ &\leq e(G[S])-\sum_{i=1}^{q}e(G[C_i])-k|A|-\frac{k|R|}{2}\\ &\leq0, \end{aligned}

where the second last inequality follows from (9) and the last inequality holds since AA separates the components of G[S]−AG[S]-A, and therefore all edges between AA and the CiC_i’s or RR, as well as edges within AA, are counted in the term k∣A∣k|A|, while the edges within RR are counted in the term k∣R∣/2k|R|/2. Thus, ex⁡k(S)≤∑i=1qex⁡k(Ci)\operatorname{ex}_k(S)\leq\sum_{i=1}^{q}\operatorname{ex}_k(C_i) and ∑i=1q∣Ci∣<∣S∣\sum_{i=1}^{q}|C_i|<|S| (as clearly ∣A∣>0|A|>0). Replacing SS in P\mathcal{P} by those CiC_i with ex⁡k(Ci)>0\operatorname{ex}_k(C_i)>0 therefore does not decrease the total excess and strictly decreases the total size, a contradiction to the fact that P\mathcal{P} is an extremal packing. Thus, G[S]G[S] is factor-critical.

Property (i) follows directly from the choice of P\mathcal{P}. Indeed, if ∑jex⁡k(Tj)>ex⁡k(S)\sum_j\operatorname{ex}_k(T_j)>\operatorname{ex}_k(S), we can replace SS with the sets TjT_j in P\mathcal{P} to obtain a new family P′\mathcal{P}' with

∑U∈P′ex⁡k(U)−∑U∈Pex⁡k(U)=∑jex⁡k(Tj)−ex⁡k(S)>0,\sum_{U\in\mathcal{P}'}\operatorname{ex}_k(U)-\sum_{U\in\mathcal{P}}\operatorname{ex}_k(U)=\sum_j\operatorname{ex}_k(T_j)-\operatorname{ex}_k(S)>0,

a contradiction to the maximality of ∑S∈Pex⁡k(S)\sum_{S\in\mathcal{P}}\operatorname{ex}_k(S).

It remains to show that (ii) holds. Consider a vertex s∈V(Q)s\in V(Q) obtained by contracting a set S∈PS\in\mathcal{P}. Then, dQ(s)d_Q(s) is equal to

eG(S,V(G)∖S)=∑v∈S(dG(v)−dG[S](v))≤∑v∈S(k−dG[S](v))=k∣S∣−2e(G[S])=k−2ex⁡k(S),e_G(S,V(G)\setminus S)=\sum_{v\in S}\left(d_G(v)-d_{G[S]}(v)\right)\leq\sum_{v\in S}\left(k-d_{G[S]}(v)\right)=k|S|-2e(G[S])=k-2\operatorname{ex}_k(S),

which is less than kk. In addition, the degrees of all vertices not obtained by contraction remain unchanged. Therefore, Δ(Q)≤k\Delta(Q)\leq k.

Now we show that QQ has no overfull odd sets. Suppose for a contradiction that there is an overfull odd set T⊆V(Q)T\subseteq V(Q), and let U⊆V(G)U\subseteq V(G) be its corresponding vertex set in GG. As all contracted sets have odd order, ∣U∣|U| is odd. Moreover, UU is an overfull odd set in GG as

ex⁡kG(U)=e(G[U])−k(∣U∣−1)2=e(Q[T])+∑S∈PS⊆Ue(G[S])−k2(∣T∣−1+∑S∈PS⊆U(∣S∣−1))=ex⁡kQ(T)+∑S∈PS⊆Uex⁡kG(S)>∑S∈PS⊆Uex⁡kG(S),\begin{aligned} \operatorname{ex}_k^G(U) &=e(G[U])-\frac{k(|U|-1)}{2}\\ &=e(Q[T])+\sum_{\substack{S\in\mathcal{P}\\S\subseteq U}}e(G[S])-\frac{k}{2}\left(|T|-1+\sum_{\substack{S\in\mathcal{P}\\S\subseteq U}}(|S|-1)\right)\\ &=\operatorname{ex}_k^Q(T)+\sum_{\substack{S\in\mathcal{P}\\S\subseteq U}}\operatorname{ex}_k^G(S)\\ &>\sum_{\substack{S\in\mathcal{P}\\S\subseteq U}}\operatorname{ex}_k^G(S), \end{aligned}

where the last inequality holds as TT is an overfull odd set in QQ (and therefore ex⁡kQ(T)>0\operatorname{ex}^{Q}_{k}(T)>0).

Thus, replacing all sets S∈PS\in\mathcal{P} with S⊆US\subseteq U by UU gives us a new family P′\mathcal{P}' with

∑S∈P′ex⁡k(S)−∑S∈Pex⁡k(S)=ex⁡k(U)−∑S∈PS⊆Uex⁡kG(S)>0,\sum_{S\in\mathcal{P}'}\operatorname{ex}_{k}(S)-\sum_{S\in\mathcal{P}}\operatorname{ex}_{k}(S)=\operatorname{ex}_{k}(U)-\sum_{\substack{S\in\mathcal{P}\\S\subseteq U}}\operatorname{ex}^{G}_{k}(S)>0,

a contradiction to the maximality of ∑S∈Pex⁡k(S)\sum_{S\in\mathcal{P}}\operatorname{ex}_{k}(S). This completes the proof of (i) and therefore that of this lemma.

Local bisections and boundary costs

A near-perfect matching exposing vv is vv-optimal if its weight is maximum among all perfect matchings of H−vH-v.

Lemma 4.1. Let kk be a positive odd integer, G=(V(G),E(G),wG)G=(V(G),E(G),w_G) a graph with nonnegative real weights and with maximum degree at most kk, and P\mathcal{P} an extremal packing in GG. For every S∈PS\in\mathcal{P} and v∈Sv\in S, let ava_v be the maximum weight of a perfect matching of G[S]−vG[S]-v. Then, there exist bG[S]≥max⁡v∈Savb_{G[S]}\ge\max_{v\in S}a_v and a random ±1\pm1 signing (Zv)v∈S(Z_v)_{v\in S} with ∑v∈SZv=1\sum_{v\in S}Z_v=1 such that

2E[wG(XS,YS)]−wG(G[S])=bG[S]andE[Zv]≥0(for all v∈S),(10)2\mathbb{E}[w_G(X_S,Y_S)]-w_G(G[S])=b_{G[S]}\quad\text{and}\quad\mathbb{E}[Z_v]\ge0\quad\text{(for all }v\in S\text{)}, \tag*{(10)}

where XS={v∈S:Zv=1}X_S=\{v\in S:Z_v=1\} and YS=S∖XSY_S=S\setminus X_S. The nonnegative penalties tv=bG[S]−avt_v=b_{G[S]}-a_v satisfy

wG(G[S])+∑v∈S(k−dG[S](v))tv≤kbG[S].(11)w_G(G[S])+\sum_{v\in S}(k-d_{G[S]}(v))t_v\le kb_{G[S]}. \tag*{(11)}

Proof. Fix S∈PS\in\mathcal{P}. By Lemma 3.1, G[S]G[S] is factor-critical. Let ν=max⁡v∈Sav\nu=\max_{v\in S}a_v and qv=ν−av≥0q_v=\nu-a_v\ge0. Define a graph HH with V(H)=SV(H)=S, E(H)=E(G[S])E(H)=E(G[S]) and weights

wH(uv):=wG[S](uv)−qu−qv.w_H(uv):=w_{G[S]}(uv)-q_u-q_v.

Thus, for every v∈Sv\in S, the maximum weight of a perfect matching of H−vH-v is

av−∑u≠vqu=(av−ν)+ν−∑u≠vqu=ν−∑uqu,a_v-\sum_{u\ne v}q_u=(a_v-\nu)+\nu-\sum_{u\ne v}q_u=\nu-\sum_u q_u,

which is the same constant c:=ν−∑uquc:=\nu-\sum_u q_u. Thus, applying Lemma 2.4 to HH, we obtain L\mathcal{L}, zT>0z_T>0, λ\lambda, and se≥0s_e\ge0 satisfying (3)–(4). Subtracting kk times (4) from the sum of (3) gives

wH(H)−kc=(e(H)−k(∣S∣−1)2)λ+∑T∈L(e(G[T])−k(∣T∣−1)2)zT−∑e∈E(H)se=ex⁡k(S)λ+∑T∈Lex⁡k(T)zT−∑e∈E(H)se.(12)\begin{aligned} w_H(H)-kc &=\left(e(H)-\frac{k(|S|-1)}{2}\right)\lambda+\sum_{T\in\mathcal{L}}\left(e(G[T])-\frac{k(|T|-1)}{2}\right)z_T-\sum_{e\in E(H)}s_e\\ &=\operatorname{ex}_k(S)\lambda+\sum_{T\in\mathcal{L}}\operatorname{ex}_k(T)z_T-\sum_{e\in E(H)}s_e. \tag*{(12)} \end{aligned}

We call an undirected edge rx∈E(H)rx\in E(H) free if there exists a vertex y∈S∖{r,x}y\in S\setminus\{r,x\} such that some rr-optimal matching contains xyxy but ry∉E(H)ry\notin E(H). Let

γ=max⁡({0}∪{wH(e):e is free}).\gamma=\max\left(\{0\}\cup\{w_H(e):e\text{ is free}\}\right).

Claim 4.2. For every overfull T∈L∪{S}T\in\mathcal{L}\cup\{S\}, there are at least ex⁡k(T)\operatorname{ex}_k(T) distinct free edges in G[T]G[T].

Proof. Note that the number of vertices in G[T]G[T] with degree kk is at least

∑v∈T(dG[T](v)−(k−1))=2e(G[T])−k∣T∣+∣T∣=2ex⁡k(T)−k+∣T∣.\sum_{v\in T}\left(d_{G[T]}(v)-(k-1)\right)=2e(G[T])-k|T|+|T|=2\operatorname{ex}_{k}(T)-k+|T|.

We now show that every such vertex is incident with at least one free edge. Indeed, for every vertex rr with dG[T](r)=kd_{G[T]}(r)=k, consider a rr-optimal matching. If T∈LT\in\mathcal{L}, then by Lemma 2.4, this matching contains exactly (∣T∣−1)/2(|T|-1)/2 edges in G[T]G[T], and hence induces a perfect matching of G[T]−rG[T]-r. If T=ST=S, the same conclusion holds since the matching exposes rr in HH. Since rr has exactly kk neighbors in TT and kk is odd, some matching edge xyxy has exactly one endpoint, say xx, in the neighborhood of rr. Thus, rxrx is a free edge in G[T]G[T].

Since each free edge can be obtained from at most two choices of rr, and ∣T∣≥k+2|T|\ge k+2 by (7) as TT is overfull, the number of distinct free edges in G[T]G[T] is at least

ex⁡k(T)+∣T∣−k2≥ex⁡k(T)+1,\operatorname{ex}_{k}(T)+\frac{|T|-k}{2}\ge\operatorname{ex}_{k}(T)+1,

completing the proof of the claim.

Now consider the laminar tree consisting of all overfull sets in L\mathcal{L}, together with SS as its root. For each set TT in this tree, define recursively, starting from the leaves,

ρ(T)=max⁡{ex⁡k(T),∑C child of Tρ(C)}.\rho(T)=\max\left\{\operatorname{ex}_{k}(T),\sum_{C\text{ child of }T}\rho(C)\right\}.

By the recursive definition, ρ(S)\rho(S) is the sum of the excesses of some pairwise disjoint overfull subsets of SS. Thus, Lemma 3.1(i) gives ρ(S)≤ex⁡k(S)\rho(S)\le\operatorname{ex}_{k}(S) and hence ρ(S)=ex⁡k(S)\rho(S)=\operatorname{ex}_{k}(S).

We next choose ρ(T)\rho(T) distinct free edges in G[T]G[T] for every set TT in the tree, starting from the leaves. It is possible to choose ρ(L)\rho(L) distinct free edges for every leaf LL by Claim 4.2, as clearly ρ(L)=ex⁡k(L)\rho(L)=\operatorname{ex}_{k}(L) in this case. Suppose the edges have already been chosen for the children of TT. Since these children are disjoint, together they contribute ∑C child of Tρ(C)\sum_{C\text{ child of }T}\rho(C) distinct free edges in G[T]G[T]. If this number is less than ρ(T)\rho(T), then ρ(T)=ex⁡k(T)\rho(T)=\operatorname{ex}_{k}(T), and Claim 4.2 guarantees that there are enough free edges in G[T]G[T] to complete the selection. Thus, at the root SS, we obtain a set FF of exactly ex⁡k(S)\operatorname{ex}_{k}(S) free edges such that

∣F∩E(G[T])∣≥ex⁡k(T)for every T∈L,|F\cap E(G[T])|\ge\operatorname{ex}_{k}(T)\qquad\text{for every }T\in\mathcal{L},

since the inequality is automatic when TT is not overfull, i.e., ex⁡k(T)≤0\operatorname{ex}_{k}(T)\le0.

By (3) and the choice of FF, we have

∑e∈Fse=ex⁡k(S)λ+∑T∈L∣F∩E(G[T])∣zT−∑e∈FwH(e)≥ex⁡k(S)λ+∑T∈Lex⁡k(T)zT−ex⁡k(S)γ.\begin{aligned} \sum_{e\in F}s_e=\operatorname{ex}_{k}(S)\lambda+\sum_{T\in\mathcal{L}}|F\cap E(G[T])|z_T-\sum_{e\in F}w_H(e) \\ &\ge\operatorname{ex}_{k}(S)\lambda+\sum_{T\in\mathcal{L}}\operatorname{ex}_{k}(T)z_T-\operatorname{ex}_{k}(S)\gamma. \end{aligned}

Since se≥0s_e\ge0 for all e∈E(H)e\in E(H), combining this with (12) gives wH(H)−kc≤ex⁡k(S)γw_H(H)-k c\le\operatorname{ex}_{k}(S)\gamma. Recall that c=ν−∑v∈Sqvc=\nu-\sum_{v\in S}q_v and wH(H)=wG(G[S])−∑v∈SdG[S](v)qvw_H(H)=w_G(G[S])-\sum_{v\in S}d_{G[S]}(v)q_v. Therefore,

wG(G[S])−kν+∑v∈S(k−dG[S](v))qv≤ex⁡k(S)γ.(13)w_G(G[S])-k\nu+\sum_{v\in S}\left(k-d_{G[S]}(v)\right)q_v\le\operatorname{ex}_{k}(S)\gamma. \tag*{(13)}

Let bG[S]=ν+γ/2b_{G[S]}=\nu+\gamma/2. We now construct a random signing satisfying (10). If γ=0\gamma=0, choose a vertex r∈Sr\in S with ar=νa_r=\nu and a rr-optimal matching, put rr on the +1+1 side, and independently assign to each matching pair (Zx,Zy)=(+1,−1)(Z_x,Z_y)=(+1,-1) or (−1,+1)(-1,+1), each with probability 1/21/2. Then ∑v∈SZv=1\sum_{v\in S} Z_v = 1, the expected surplus is ν=bG[S]\nu= b_{G[S]}, and E[Zr]=1\mathbb{E}[Z_r] = 1 while E[Zv]=0\mathbb{E}[Z_v] = 0 for every v≠rv \ne r. Hence (10) holds.

Otherwise, let rxrx be a free edge with wH(rx)=γ>0w_H(rx) = \gamma> 0, witnessed by a rr-optimal matching that contains xyxy, where ry∉E(H)ry \notin E(H). Consider the following two random signings:

(a) Put r,yr,y on the +1+1 side and xx on the −1-1 side, and independently assign to each remaining matching pair (Zu,Zv)=(+1,−1)(Z_u,Z_v) = (+1,-1) or (−1,+1)(-1,+1), each with probability 1/21/2.

(b) Choose an xx-optimal matching, put xx on the +1+1 side, and independently assign to each matching pair (Zu,Zv)=(+1,−1)(Z_u,Z_v) = (+1,-1) or (−1,+1)(-1,+1), each with probability 1/21/2.

Both signings have sum 11. In (a), all matching edges and rxrx are included in the cut, while no edge is forced to be excluded since ry∉E(H)ry \notin E(H). Thus, its expected surplus is ar+wG(rx)a_r + w_G(rx), while in (b) it is axa_x.

Now choose (a) or (b), each with probability 1/21/2. Since Zr=Zy=1Z_r = Z_y = 1 and Zx=−1Z_x = -1 in (a), while Zx=1Z_x = 1 and E[Zv]=0\mathbb{E}[Z_v] = 0 for every v≠xv \ne x in (b), we have E[Zr]=E[Zy]=1/2\mathbb{E}[Z_r] = \mathbb{E}[Z_y] = 1/2 and E[Zv]=0\mathbb{E}[Z_v] = 0 for every v∉{r,y}v \notin\{r,y\}. Thus, E[Zv]≥0\mathbb{E}[Z_v] \ge0 for all v∈Sv \in S. Moreover, the expected surplus is

ar+wG(rx)+ax2=ν+wG(rx)−qr−qx2=ν+γ2=bG[S].\frac{a_r+w_G(rx)+a_x}{2}=\nu+\frac{w_G(rx)-q_r-q_x}{2}=\nu+\frac{\gamma}{2}=b_{G[S]}.

This completes the proof of (10).

Finally, since tv=bG[S]−av=qv+γ/2≥0t_v=b_{G[S]}-a_v=q_v+\gamma/2\ge0, it follows from (13) that

wG(G[S])+∑v∈S(k−dG[S](v))tv≤kν+ex⁡k(S)γ+γ2∑v∈S(k−dG[S](v))=kν+ex⁡k(S)γ+γ2(k−2ex⁡k(S))=kbG[S].\begin{aligned} w_G(G[S])+\sum_{v\in S}(k-d_{G[S]}(v))t_v\le k\nu+\operatorname{ex}_k(S)\gamma+\frac{\gamma}{2}\sum_{v\in S}(k-d_{G[S]}(v)) \\ &= k\nu+\operatorname{ex}_k(S)\gamma+\frac{\gamma}{2}(k-2\operatorname{ex}_k(S)) \\ &=kb_{G[S]}. \end{aligned}

This proves (11) and completes the proof.

Proof of the main theorem

Now, we are ready to give the proof of our main result.

Proof of Theorem 1.1. Let P\mathcal{P} be a family of pairwise disjoint overfull odd vertex sets that maximizes ∑S∈Pex⁡k(S)\sum_{S\in\mathcal{P}}\operatorname{ex}_k(S) and, subject to this, minimizes ∑S∈P∣S∣\sum_{S\in\mathcal{P}}|S|. For every S∈PS\in\mathcal{P}, let bG[S]b_{G[S]}, ava_v and tvt_v (v∈Sv\in S) be as in Lemma 4.1. For every v∉⋃S∈PSv\notin\bigcup_{S\in\mathcal{P}}S, let tv=0t_v=0.

Contract all sets in P\mathcal{P} to obtain a multigraph QQ, retaining all external edges separately. Let cc be the natural bijection from the edges of GG surviving the contraction to E(Q)E(Q). For every such edge ee with endpoints uu and vv, assign

wQ(c(e)):=wG(e)−tu−tv.w_Q(c(e)):=w_G(e)-t_u-t_v.

Then, by Lemma 3.1(ii), QQ has maximum degree at most kk and no overfull odd vertex sets. Thus, by Corollary 2.2, QQ has a matching M′M' with

wQ(M′)≥wQ(Q)k.(14)w_Q(M')\ge\frac{w_Q(Q)}{k}. \tag*{(14)}

Now we lift M′M' to a matching MM of GG. Let C⊆V(Q)C\subseteq V(Q) be the set of new vertices obtained from the contraction. For every e∈M′e\in M', let uu and vv be the endpoints of c−1(e)c^{-1}(e) in GG, and include c−1(e)c^{-1}(e) in MM. If u∈Su\in S for some S∈PS\in\mathcal{P}, then we also include a maximum-weight perfect matching of G[S]−uG[S]-u, whose weight is aua_u. We do the same for vv if it belongs to some set in P\mathcal{P}. Since M′M' is a matching, the resulting set MM is also a matching of GG. For any edge $e\in M with endpoints xx and yy, we independently assign (Xx,Xy)(X_x, X_y) to be (+1,−1)(+1,-1) or (−1,+1)(-1,+1) with probability 1/21/2.

It remains to assign signs to the vertices not covered by MM. Let U\mathcal{U} be the family of vertex sets of GG corresponding to the vertices of QQ not covered by M′M'. Each A∈UA \in\mathcal{U} is either a set in P\mathcal{P} or a singleton vertex outside all sets in P\mathcal{P}. For every A∈UA \in\mathcal{U}, we independently choose a random signing (Zx)x∈A(Z_x)_{x\in A} such that ∑x∈AZx=1\sum_{x\in A} Z_x = 1 and E(Zx)≥0\mathbb{E}(Z_x) \ge0 for all x∈Ax \in A: If A∈PA \in\mathcal{P}, we use the probability space given by Lemma 4.1; if A={u}A = \{u\} is a singleton, we simply set Zu=1Z_u = 1.

We pair the sets in U\mathcal{U} arbitrarily so that at most one set is left over. For every paired two sets A,B∈UA,B \in\mathcal{U}, we put their larger partite sets on opposite sides. More precisely, we independently choose a uniform random sign σ∈{−1,+1}\sigma\in\{-1,+1\} and set Xx=σZxX_x = \sigma Z_x for x∈Ax \in A and Xy=−σZyX_y = -\sigma Z_y for y∈By \in B. If one set AA remains unpaired, we choose another independent uniform random sign σ\sigma and set Xx=σZxX_x = \sigma Z_x for all x∈Ax \in A. Since each signing (Zx)x∈A(Z_x)_{x\in A} has sum 11, the resulting signing XX gives a bisection (X−1(+1),X−1(−1))(X^{-1}(+1),X^{-1}(-1)) of GG.

Now consider any external edge ee with endpoints x∈Ax \in A and y∈By \in B, where A,B∈UA,B \in\mathcal{U} are paired together. We claim that such edges are included in this random bisection with probability at least 1/21/2. Indeed, it is easy to check that 1−XxXy2\frac{1-X_xX_y}{2} is the indicator for whether this edge is included in the bisection. Thus,

Pr⁡[e is included]=E[1−XxXy2]=E[1+ZxZy2]=1+E[Zx]E[Zy]2≥12.\Pr[e\text{ is included}] = \mathbb{E}\left[\frac{1-X_xX_y}{2}\right] = \mathbb{E}\left[\frac{1+Z_xZ_y}{2}\right] = \frac{1+\mathbb{E}[Z_x]\mathbb{E}[Z_y]}{2} \ge\frac{1}{2}.

where the last inequality follows from Lemma 4.1 and the definition of ZZ for singleton sets.

Every edge in MM is always included in the bisection. Now consider an external edge ee not in MM. If at least one endpoint of ee is covered by MM, then since we independently assigned to +1+1 or −1-1 to the random variable corresponding to its endpoint in MM with probability 1/21/2, it is easy to show that ee is included with probability exactly 1/21/2. Otherwise, both endpoints of ee belong to sets in U\mathcal{U}, say AA and BB. If AA and BB are paired together, we have already shown that ee is included with probability at least 1/21/2. If not, the signs of its endpoints are independent and uniformly distributed over {−1,+1}\{-1,+1\}, since the random signs σ\sigma assigned to different pairs are independent and uniform. Hence, ee is included with probability exactly 1/21/2. Consequently, every external edge not in MM is included with probability at least 1/21/2.

Now consider the surplus contributed by the internal edges of the sets in P\mathcal{P} and the external edges in MM. Let ee be an edge of GG with c(e)∈M′c(e) \in M' and endpoints u∈Suu \in S_u and v∈Svv \in S_v, where Su,Sv∈PS_u,S_v \in\mathcal{P}. Since ee and the two chosen internal matchings are always included in the bisection, while all other internal edges of these two sets are included with probability 1/21/2, their total contribution to the surplus is

wG(e)+au+av=bG[Su]+bG[Sv]−tu−tv+wG(e)=wQ(c(e))+bG[Su]+bG[Sv].w_G(e)+a_u+a_v=b_G[S_u]+b_G[S_v]-t_u-t_v+w_G(e)=w_Q(c(e))+b_G[S_u]+b_G[S_v].

If one or both endpoints of ee do not belong to any set in P\mathcal{P}, the same calculation holds by omitting the corresponding terms. On the other hand, every set S∈PS \in\mathcal{P} whose contracted vertex is not covered by M′M' contributes an expected surplus of bG[S]b_G[S] as we used the probability space in Lemma 4.1 for it. Since all other external edges contribute a nonnegative expected surplus, summing over all edges in M′M' and all unmatched sets in P\mathcal{P} gives

2E[wG(X−1(+1),X−1(−1))]−wG(G)≥∑S∈PbG[S]+wQ(M′)≥∑S∈PbG[S]+wQ(Q)k.(15)2\mathbb{E}[w_G(X^{-1}(+1),X^{-1}(-1))]-w_G(G) \ge\sum_{S\in\mathcal{P}} b_G[S]+w_Q(M') \ge\sum_{S\in\mathcal{P}} b_G[S]+\frac{w_Q(Q)}{k}. \tag*{(15)}

where the last inequality follows from (5.1).

On the other hand, as wQ(c(e))=wG(e)−tu−tvw_Q(c(e))=w_G(e)-t_u-t_v for every edge ee surviving the contraction, where uu and vv are its endpoints in GG, we have

wG(G)=wQ(Q)+∑S∈P(wG(G[S])+∑u∈Se(u,V(G)∖S)tu)≤wQ(Q)+∑S∈P(wG(G[S])+∑u∈S(k−dG[S](u))tu)≤wQ(Q)+k∑S∈PbG[S].(16)\begin{aligned} w_G(G) &= w_Q(Q) + \sum_{S \in\mathcal{P}} \left( w_G(G[S]) + \sum_{u \in S} e(u,V(G)\setminus S)t_u \right) \\ &\le w_Q(Q) + \sum_{S \in\mathcal{P}} \left( w_G(G[S]) + \sum_{u \in S} (k-d_{G[S]}(u))t_u \right) \\ &\le w_Q(Q) + k\sum_{S \in\mathcal{P}} b_{G[S]}. \tag*{(16)} \end{aligned}

where the first inequality follows from the fact that Δ(G)≤k\Delta(G) \le k (and therefore e({u},V(G)∖S)≤k−dG[S]e(\{u\},V(G)\setminus S) \le k-d_{G[S]}) and tu≥0t_u \ge0, and the second follows from Lemma 4.1.

Combining (15) and (16), we obtain

E[wG(X−1(+1),X−1(−1))]≥wG(G)2+12(∑S∈PbG[S]+wQ(Q)k)≥k+12kwG(G).\mathbb{E}[w_G(X^{-1}(+1),X^{-1}(-1))] \ge\frac{w_G(G)}{2}+\frac{1}{2}\left(\sum_{S\in\mathcal{P}}b_{G[S]}+\frac{w_Q(Q)}{k}\right)\ge\frac{k+1}{2k}w_G(G).

Hence there exists a bisection of GG with weight at least (k+1)wG(G)/(2k)(k+1)w_G(G)/(2k), as desired. □

Concluding remarks

Theorem 1.1 and Corollary 1.2 show that the sharp maximum-degree coefficients for unrestricted cuts also hold for bisections with arbitrary nonnegative edge weights. The proof does not require the graph to be regular or connected.

Corollary 2.3 settles the case without overfull odd sets directly by combining the matching-polytope theorem with the matching-to-bisection bound. The rest of the proof reduces the general case to a quotient with no overfull odd set while controlling the losses in expanding the contracted blocks.

The local inequality (11) accounts for the loss incurred when a prescribed vertex must be exposed in a selected block. After assigning each external edge uvuv the adjusted weight wG(uv)−tu−tvw_G(uv)-t_u-t_v, the matching-polytope bound gives a quotient matching of weight at least wQ(Q)/kw_Q(Q)/k. Lifting this matching and applying the local boundary-cost inequality completes the proof.

Declaration on the Use of Generative AI

The authors used ChatGPT 6 Astra to assist in discussing proof strategies and checking proofs. The authors take full responsibility for the content of the manuscript.

References

  1. [1]L.D. Anderson, D. Grant, and N. Linial, Extremal k-colourable subgraphs, Ars Combinatoria 16 (1983), 259–270.
  2. [2]B. Bollobás and A. D. Scott, Judicious partitions of bounded-degree graphs, Journal of Graph Theory 46 (2004), no. 2, 131–143.
  3. [3]J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices, Journal of Research of the National Bureau of Standards, Section B 69B (1965), 125–130.
  4. [4]S. Gerke, G. Gutin, A. Yeo, and Y. Zhou, Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees, arXiv:2401.10074v2, 2024.arxiv.org/abs/2401.10074
  5. [5]Q. Guo and G. Gutin, Sharp lower bounds for bisections of graphs with bounded maximum degree, arXiv:2610.15024, 2026.arxiv.org/abs/2610.15024
  6. [6]C. Lee, P.-S. Loh, and B. Sudakov, Bisections of graphs, Journal of Combinatorial Theory, Series B 103 (2013), no. 5, 599–629.
  7. [7]J. Lehel and Zs. Tuza, Triangle-free partial graphs and edge-covering theorems, Discrete Mathematics 39 (1982), no. 1, 59–65.DOI
  8. [8]S. C. Locke, Maximum k-colorable subgraphs, Journal of Graph Theory 6 (1982), no. 2, 123–132.DOI
  9. [9]W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22 (1947), no. 2, 107–111.DOI

Paper details

vlnc:W_kzhrc8b8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 6 Astra

View statement
Looking for related papers…
Contents