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 , with arbitrary nonnegative real edge weights, has a bisection of weight at least times its total edge weight. The corresponding bound for even 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 be a graph with an edge-weight function . Write . A cut is the set of edges joining the two parts of a partition of . A cut is a bisection if the part sizes differ by at most one. Let denote the maximum weight of a bisection of , and let denote the maximum weight of an unrestricted cut. Thus .
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 . A natural question is how much the maximum-degree bound improves this estimate.
Classical results on cuts in graphs with chromatic number [1, 7, 8] give a cut with at least a proportion
of all edges, for . The same argument gives for arbitrary nonnegative edge weights. Indeed, fix a proper -coloring and choose uniformly a set of colors for one part, placing the remaining colors in the other part. Every edge joins distinct colors and is separated with probability
Linearity of expectation proves the weighted bound. If has no edges, the corresponding weighted statements are immediate.
In particular, a proper -coloring of a graph with maximum degree at most yields
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 with unit weights, the maximum cut contains all edges, whereas every bisection has at most 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 for -regular graphs when is odd. Their proof cannot be extended to the weighted case.
Our main result resolves this case.
Theorem 1.1. Let be an odd positive integer. Every graph with and nonnegative real edge weights satisfies
Applying Theorem 1.1 with instead of gives the following previously known even-degree bound as an immediate consequence.
Corollary 1.2. Let be a positive even integer. Every graph with and nonnegative real edge weights satisfies
Together these statements establish [4 Conjecture 1.1] in full: the balance requirement causes no loss in the sharp universal weighted-cut coefficients . Both coefficients are best possible: with unit weights, and every bisection of has weight , so
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 , write , counting parallel edges separately. For disjoint vertex sets , let 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 is factor-critical if has a perfect matching for every . 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, is a fixed odd positive integer. For every odd vertex set in a graph , let the excess of be defined as follows
We call overfull if , 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 leaves at most odd components.
Note that if is a matching in then the incidence vector of is with if and , otherwise. The first two conditions in Theorem 2.1 describe all matchings of provided all are integral. The third condition is needed in order to get the convex hull when we allow all to be real.
Theorem 2.1 (Edmonds [3]). For a loopless multigraph , the convex hull of the incidence vectors of its matchings is described by
Corollary 2.2. Let be a loopless multigraph with maximum degree at most and no overfull odd set. For every real edge weighting, has a matching of weight at least .
Proof. The vector with satisfies (2). Its weighted objective is , and some matching has at least this weight by Theorem 2.1. □
Corollary 2.3. Let be an odd integer, let be a simple graph with maximum degree at most , and suppose that has no overfull odd set. Then, for every nonnegative edge weighting,
Proof. By Corollary 2.2, there is a matching with . The matching-to-bisection bound of Gerke, Gutin, Yeo and Zhou [4 Corollary 2.3] gives
For completeness, the first inequality follows by pairing the endpoints of each edge of , 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 . □
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 be a factor-critical graph of odd order , with real edge weights . Suppose that, for every vertex , the maximum weight of a perfect matching of is the same number . Then, there exist a laminar family of proper odd vertex sets, positive numbers for , a real number , and nonnegative slacks , such that
and
Moreover, every near-perfect matching of weight contains exactly edges of for each .
Proof. Choose and replace the edge weight of each edge by
For any two matchings , we have . Thus, under the new weights, a matching with more edges always has larger weight. In particular, every maximum-weight matching now has edges. By Theorem 2.1, the maximum-weight matching problem is equivalent to the following linear program:
Thus, its dual is
Here and are the dual variables corresponding to the vertex constraints and the odd-set constraints, respectively.
For every , let be a maximum-weight perfect matching of , and let denote its characteristic vector, i.e., if and otherwise. By our assumption, all these matchings have the same original weight , and hence their characteristic vectors are optimal solutions of (P). Since every is optimal for (P), their average is optimal for (P). Moreover, for every , we have
where the last equality holds since contains exactly one edge incident with when , while contains none. Thus, the complementary slackness theorem implies that every optimal solution of (D) satisfies
Among all optimal solutions of (D), choose one minimizing the potential
Such a choice is possible since the optimal dual solutions form a nonempty polyhedron and . Let .
Claim 2.5. is a laminar family.
Proof. Suppose, for a contradiction, that there are two crossing sets , i.e., , and are all nonempty. Let and .
First suppose that is even. Since and are odd, both and are odd. We decrease by , increase by , and increase by for every . We claim that every dual constraint remains satisfied. Indeed, for any edge , if both endpoints are in , then the decrease of and is compensated by the increase of and . If both endpoints are in or both are in , then the decrease of or is compensated by the increase of or , respectively. If one endpoint is in and the other is in or , then the decrease of or is compensated by the increase of the vertex variable at the endpoint in . For all other edges, the left-hand side of the dual constraint does not decrease. Moreover, the dual objective remains unchanged, since
Thus, we obtain another optimal solution of (D) with for every , contradicting (6).
Now suppose that is odd. Then both and are odd. We decrease by and increase by . Again, we claim that every dual constraint remains satisfied. Indeed, for any edge , if both endpoints are in , then the decrease of is compensated by the increase of . If both endpoints are in or both are in , or if one endpoint is in and the other is in or , then the decrease of or is compensated by the increase of . If one endpoint is in and the other is in , then the left-hand side of the dual constraint increases by (due to ). For all remaining edges, it remains unchanged. Moreover, the dual objective remains unchanged as . However, the potential decreases by
where the second equality follows from . This contradicts the minimality of . Thus, no two sets in cross, and hence is laminar.
Let and . Note that if . Thus, for every edge , by (5), (6) and the definition of , we have
Let be the slack in this inequality. Then, by the definitions of , and , we obtain (3).
On the other hand, by strong duality, the optimal value of (P) equals the optimal value of (D). Recall that every maximum-weight matching under the new weights is near-perfect, and the maximum original weight of a near-perfect matching is . Thus, . In addition, by (6),
where the last equality follows from the definition of . Thus,
Substituting gives (4).
Finally, let be any near-perfect matching of weight . Then is optimal for (P) under the new weights. Since for every , the complementary slackness theorem implies that the corresponding odd-set constraint is tight for , i.e.,
This completes the proof.
An extremal packing of odd sets
In this section, we always assume that is a positive odd integer and is a weighted graph with maximum degree at most . A family of pairwise disjoint overfull odd vertex sets in is called an extremal packing if it maximizes and, subject to this, minimizes . The empty family is allowed.
Note that every overfull odd set satisfies
and therefore . Since both and are odd, we have
Lemma 3.1. Let be an extremal packing in . Then every , , is factor-critical. Moreover:
(i) for every and every family of pairwise disjoint overfull odd subsets ,
(ii) contracting all members of , and retaining each original external edge separately, gives a loopless multigraph with maximum degree at most and no overfull odd set.
Proof. Fix an arbitrary . We first show that is factor-critical. Suppose, for a contradiction, that there exists a vertex such that has no perfect matching. Then, by Tutte’s theorem, there is a subset such that has odd components . Since is even, and must have the same parity, and hence . Let . Then
Let be the union of all even components of . Thus,
where the second last inequality follows from (9) and the last inequality holds since separates the components of , and therefore all edges between and the ’s or , as well as edges within , are counted in the term , while the edges within are counted in the term . Thus, and (as clearly ). Replacing in by those with therefore does not decrease the total excess and strictly decreases the total size, a contradiction to the fact that is an extremal packing. Thus, is factor-critical.
Property (i) follows directly from the choice of . Indeed, if , we can replace with the sets in to obtain a new family with
a contradiction to the maximality of .
It remains to show that (ii) holds. Consider a vertex obtained by contracting a set . Then, is equal to
which is less than . In addition, the degrees of all vertices not obtained by contraction remain unchanged. Therefore, .
Now we show that has no overfull odd sets. Suppose for a contradiction that there is an overfull odd set , and let be its corresponding vertex set in . As all contracted sets have odd order, is odd. Moreover, is an overfull odd set in as
where the last inequality holds as is an overfull odd set in (and therefore ).
Thus, replacing all sets with by gives us a new family with
a contradiction to the maximality of . This completes the proof of (i) and therefore that of this lemma.
Local bisections and boundary costs
A near-perfect matching exposing is -optimal if its weight is maximum among all perfect matchings of .
Lemma 4.1. Let be a positive odd integer, a graph with nonnegative real weights and with maximum degree at most , and an extremal packing in . For every and , let be the maximum weight of a perfect matching of . Then, there exist and a random signing with such that
where and . The nonnegative penalties satisfy
Proof. Fix . By Lemma 3.1, is factor-critical. Let and . Define a graph with , and weights
Thus, for every , the maximum weight of a perfect matching of is
which is the same constant . Thus, applying Lemma 2.4 to , we obtain , , , and satisfying (3)–(4). Subtracting times (4) from the sum of (3) gives
We call an undirected edge free if there exists a vertex such that some -optimal matching contains but . Let
Claim 4.2. For every overfull , there are at least distinct free edges in .
Proof. Note that the number of vertices in with degree is at least
We now show that every such vertex is incident with at least one free edge. Indeed, for every vertex with , consider a -optimal matching. If , then by Lemma 2.4, this matching contains exactly edges in , and hence induces a perfect matching of . If , the same conclusion holds since the matching exposes in . Since has exactly neighbors in and is odd, some matching edge has exactly one endpoint, say , in the neighborhood of . Thus, is a free edge in .
Since each free edge can be obtained from at most two choices of , and by (7) as is overfull, the number of distinct free edges in is at least
completing the proof of the claim.
Now consider the laminar tree consisting of all overfull sets in , together with as its root. For each set in this tree, define recursively, starting from the leaves,
By the recursive definition, is the sum of the excesses of some pairwise disjoint overfull subsets of . Thus, Lemma 3.1(i) gives and hence .
We next choose distinct free edges in for every set in the tree, starting from the leaves. It is possible to choose distinct free edges for every leaf by Claim 4.2, as clearly in this case. Suppose the edges have already been chosen for the children of . Since these children are disjoint, together they contribute distinct free edges in . If this number is less than , then , and Claim 4.2 guarantees that there are enough free edges in to complete the selection. Thus, at the root , we obtain a set of exactly free edges such that
since the inequality is automatic when is not overfull, i.e., .
By (3) and the choice of , we have
Since for all , combining this with (12) gives . Recall that and . Therefore,
Let . We now construct a random signing satisfying (10). If , choose a vertex with and a -optimal matching, put on the side, and independently assign to each matching pair or , each with probability . Then , the expected surplus is , and while for every . Hence (10) holds.
Otherwise, let be a free edge with , witnessed by a -optimal matching that contains , where . Consider the following two random signings:
(a) Put on the side and on the side, and independently assign to each remaining matching pair or , each with probability .
(b) Choose an -optimal matching, put on the side, and independently assign to each matching pair or , each with probability .
Both signings have sum . In (a), all matching edges and are included in the cut, while no edge is forced to be excluded since . Thus, its expected surplus is , while in (b) it is .
Now choose (a) or (b), each with probability . Since and in (a), while and for every in (b), we have and for every . Thus, for all . Moreover, the expected surplus is
This completes the proof of (10).
Finally, since , it follows from (13) that
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 be a family of pairwise disjoint overfull odd vertex sets that maximizes and, subject to this, minimizes . For every , let , and () be as in Lemma 4.1. For every , let .
Contract all sets in to obtain a multigraph , retaining all external edges separately. Let be the natural bijection from the edges of surviving the contraction to . For every such edge with endpoints and , assign
Then, by Lemma 3.1(ii), has maximum degree at most and no overfull odd vertex sets. Thus, by Corollary 2.2, has a matching with
Now we lift to a matching of . Let be the set of new vertices obtained from the contraction. For every , let and be the endpoints of in , and include in . If for some , then we also include a maximum-weight perfect matching of , whose weight is . We do the same for if it belongs to some set in . Since is a matching, the resulting set is also a matching of . For any edge $e\in M with endpoints and , we independently assign to be or with probability .
It remains to assign signs to the vertices not covered by . Let be the family of vertex sets of corresponding to the vertices of not covered by . Each is either a set in or a singleton vertex outside all sets in . For every , we independently choose a random signing such that and for all : If , we use the probability space given by Lemma 4.1; if is a singleton, we simply set .
We pair the sets in arbitrarily so that at most one set is left over. For every paired two sets , we put their larger partite sets on opposite sides. More precisely, we independently choose a uniform random sign and set for and for . If one set remains unpaired, we choose another independent uniform random sign and set for all . Since each signing has sum , the resulting signing gives a bisection of .
Now consider any external edge with endpoints and , where are paired together. We claim that such edges are included in this random bisection with probability at least . Indeed, it is easy to check that is the indicator for whether this edge is included in the bisection. Thus,
where the last inequality follows from Lemma 4.1 and the definition of for singleton sets.
Every edge in is always included in the bisection. Now consider an external edge not in . If at least one endpoint of is covered by , then since we independently assigned to or to the random variable corresponding to its endpoint in with probability , it is easy to show that is included with probability exactly . Otherwise, both endpoints of belong to sets in , say and . If and are paired together, we have already shown that is included with probability at least . If not, the signs of its endpoints are independent and uniformly distributed over , since the random signs assigned to different pairs are independent and uniform. Hence, is included with probability exactly . Consequently, every external edge not in is included with probability at least .
Now consider the surplus contributed by the internal edges of the sets in and the external edges in . Let be an edge of with and endpoints and , where . Since 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 , their total contribution to the surplus is
If one or both endpoints of do not belong to any set in , the same calculation holds by omitting the corresponding terms. On the other hand, every set whose contracted vertex is not covered by contributes an expected surplus of 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 and all unmatched sets in gives
where the last inequality follows from (5.1).
On the other hand, as for every edge surviving the contraction, where and are its endpoints in , we have
where the first inequality follows from the fact that (and therefore ) and , and the second follows from Lemma 4.1.
Combining (15) and (16), we obtain
Hence there exists a bisection of with weight at least , 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 the adjusted weight , the matching-polytope bound gives a quotient matching of weight at least . 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]L.D. Anderson, D. Grant, and N. Linial, Extremal k-colourable subgraphs, Ars Combinatoria 16 (1983), 259–270.
- [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]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]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]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]C. Lee, P.-S. Loh, and B. Sudakov, Bisections of graphs, Journal of Combinatorial Theory, Series B 103 (2013), no. 5, 599–629.
- [7]J. Lehel and Zs. Tuza, Triangle-free partial graphs and edge-covering theorems, Discrete Mathematics 39 (1982), no. 1, 59–65.DOI
- [8]S. C. Locke, Maximum k-colorable subgraphs, Journal of Graph Theory 6 (1982), no. 2, 123–132.DOI
- [9]W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22 (1947), no. 2, 107–111.DOI