pith. sign in

arxiv: 2605.05346 · v1 · submitted 2026-05-06 · 🧮 math.CO

Balanced bipartite distance of K₄-free graphs

J\'ozsef Balogh , Ignacy Buczek , Andrzej Grzesik , Piotr Kuc This is my paper

Pith reviewed 2026-05-08 16:05 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords K4-free graphsbalanced bipartite graphsedge deletionbipartite distanceextremal graph theory
0
0 comments X

The pith

Every K4-free graph on n vertices can be made balanced bipartite by removing at most n²/9 edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that any graph without a K4 can be edited into a bipartite graph whose two parts have equal size by deleting no more than one-ninth of the possible edges. The bound is obtained by combining structural properties forced by the absence of K4 with careful counting of edges that cross between the intended parts. This settles an earlier conjecture and shows that two previously separate results—one on the minimum edges to delete to reach any bipartite graph and one on making one side sparse—are in fact special cases of the same phenomenon. A reader cares because the result gives a concrete, uniform measure of how close K4-free graphs are to having the simplest possible equitable bipartition.

Core claim

We show that every K4-free graph on n vertices can be made balanced bipartite by removing at most n²/9 edges. This proves a conjecture of Balogh, Clemen, and Lidický, and generalizes both Sudakov's result on the bipartite distance of K4-free graphs and Reiher's result on the sparse half of K4-free graphs.

What carries the argument

The balanced bipartite distance, i.e., the minimum number of edges that must be deleted to obtain a bipartite graph with equal part sizes; the K4-free hypothesis supplies the structural control needed to bound this distance by n²/9.

If this is right

  • The minimum number of edges to delete to reach a balanced bipartite graph is at most n²/9 for every K4-free graph.
  • The conjecture of Balogh, Clemen, and Lidický on this quantity is correct.
  • Sudakov's earlier bound on the ordinary bipartite distance of K4-free graphs follows as a special case.
  • Reiher's bound on the size of a sparse half in a K4-free graph follows as a special case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same n²/9 bound may serve as a benchmark when studying edit distances to other equitable hereditary properties in K4-free graphs.
  • Extremal examples achieving equality are likely to be obtained from balanced complete 3-partite graphs by removing all edges inside one part.

Load-bearing premise

The graph contains no four vertices that are all pairwise adjacent.

What would settle it

A single K4-free graph on n vertices whose balanced bipartite distance exceeds n²/9.

Figures

Figures reproduced from arXiv: 2605.05346 by Andrzej Grzesik, Ignacy Buczek, J\'ozsef Balogh, Piotr Kuc.

Figure 1
Figure 1. Figure 1: Different kinds of class-edges in the random biparti view at source ↗
read the original abstract

We show that every $K_4$-free graph on $n$ vertices can be made balanced bipartite by removing at most $\frac{n^2}{9}$ edges. This proves a conjecture of Balogh, Clemen, and Lidick\'{y}, and generalizes both Sudakov's result on the bipartite distance of $K_4$-free graphs and Reiher's result on the sparse half of $K_4$-free graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper proves that every K_4-free graph on n vertices can be made balanced bipartite by deleting at most n²/9 edges. This confirms a conjecture of Balogh, Clemen, and Lidický and generalizes Sudakov's bound on the bipartite distance of K_4-free graphs together with Reiher's result on their sparse halves. The argument proceeds by exploiting the extremal structure of K_4-free graphs (in particular the properties of the Turán graph T(n,3)) to produce a nearly balanced bipartition whose crossing edges differ from the target balanced bipartite graph by at most the stated number of deletions; the bound is shown to be tight.

Significance. If the proof is correct, the result supplies a sharp, parameter-free upper bound on the balanced bipartite distance of K_4-free graphs and thereby resolves an open conjecture while unifying two earlier theorems in the same extremal setting. The explicit tightness example with T(n,3) and the direct combinatorial approach (no hidden parameters or fitted constants) constitute a clean contribution to the study of forbidden-subgraph problems and the quantitative distance to bipartiteness.

minor comments (2)
  1. The abstract and introduction cite Sudakov and Reiher; verify that the bibliography entries are complete and that the precise statements being generalized are quoted or referenced with page numbers.
  2. In the tightness argument for T(n,3), confirm that the final adjustment to a balanced bipartition stays within the n²/9 budget for all residue classes of n modulo 3.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, for recognizing that the result resolves the conjecture of Balogh, Clemen, and Lidický while unifying earlier theorems of Sudakov and Reiher, and for recommending acceptance.

Circularity Check

0 steps flagged

Direct combinatorial proof; no circular reductions or load-bearing self-citations

full rationale

The manuscript establishes the balanced bipartite distance bound for K4-free graphs via a direct structural argument that decomposes the graph according to its K4-free properties and explicitly constructs a bipartition after edge deletions bounded by n²/9. This derivation relies on extremal graph theory facts about K4-free graphs (including the known tightness example T(n,3)) that are external to the present proof and do not reduce to fitted parameters, self-definitions, or ansatzes imported from the authors' prior work. The conjecture being proved is stated as an open claim rather than an assumption, and the generalizations of Sudakov and Reiher are cited as context rather than as load-bearing steps that would make the central result tautological. No equation or lemma equates a derived quantity to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests only on standard graph-theoretic definitions and combinatorial counting; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Standard axioms and definitions of graphs, subgraphs, bipartiteness, and K4-freeness.
    Invoked for all basic notions throughout the argument.

pith-pipeline@v0.9.0 · 5370 in / 1048 out tokens · 96387 ms · 2026-05-08T16:05:50.685353+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Bipartite cuts in Ramsey-Tur\'an style

    math.CO 2026-06 unverdicted novelty 7.0

    K5-free graphs on n vertices with sublinear independence number lie at most (1/18 + o(1))n² edges from bipartiteness, and 1/18 is asymptotically best possible.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    Hypergraphs Do Jump

    Rahil Baber and John Talbot. “Hypergraphs Do Jump”. In: Combinatorics, Proba- bility and Computing 20.2 (2011), pp. 161–171

    work page 2011

  2. [2]

    10 problems for par- titions of triangle-free graphs

    J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lid ick´ y. “10 problems for par- titions of triangle-free graphs”. In: European Journal of Combinatorics 121 (2024), p. 103841

    work page 2024

  3. [3]

    Max cuts in triangle- free graphs

    J´ ozsef Balogh, Felix Christian Clemen, and Bernard Lid ick´ y. “Max cuts in triangle- free graphs”. In: Extended Abstracts EuroComb 2021: European Conference on Com- binatorics, Graph Theory and Applications . Springer. 2021, pp. 509–514. 20

    work page 2021

  4. [4]

    Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

    J´ ozsef Balogh, Ping Hu, Bernard Lidick´ y, and Hong Liu. “Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube”. In: European Journal of Combinatorics 35 (2014), pp. 75–85

    work page 2014

  5. [5]

    Minimum number of monotone subsequences of length 4 in permutations

    J´ ozsef Balogh, Ping Hu, Bernard Lidick´ y, Oleg Pikhurk o, Bal´ azs Udvari, and Jan Volec. “Minimum number of monotone subsequences of length 4 in permutations”. In: Combinatorics, Probability and Computing 24.4 (2015), pp. 658–679

    work page 2015

  6. [6]

    Inducibility of 4-vertex tournaments

    Dalton Burke, Bernard Lidick´ y, Florian Pfender, and Mi chael Phillips. “Inducibility of 4-vertex tournaments”. arXiv: 2103.07047

    work page arXiv

  7. [7]

    On graphs not containing pr escribed induced subgraphs

    Fan Chung and Ronald Graham. “On graphs not containing pr escribed induced subgraphs”. In: A Tribute to Paul Erdos . Cambridge University Press, 1990, pp. 111– 120

    work page 1990

  8. [8]

    Problems and results in graph theory and co mbinatorial analysis

    Paul Erd˝ os. “Problems and results in graph theory and co mbinatorial analysis”. In: Proceedings of the Fifth British Combinatorial Conference (U niv. Aberdeen, Ab- erdeen). Vol. XV. 1975, pp. 169–192

    work page 1975

  9. [9]

    Some unsolved problems in graph theory and combinatorial analysis

    Paul Erd˝ os. “Some unsolved problems in graph theory and combinatorial analysis”. In: Combinatorial Mathematics and Its Applications (Proc. Conf., Oxford, 1969) (1971), pp. 97–109

    work page 1969

  10. [10]

    How to make a graph bipartite

    Paul Erd˝ os, Ralph Faudree, J´ anos Pach, and Joel Spenc er. “How to make a graph bipartite”. In: Journal of Combinatorial Theory, Series B 45.1 (1988), pp. 86–98

    work page 1988

  11. [11]

    A local density condition for triangles

    Paul Erd˝ os, Ralph Faudree, Cecil Rousseau, and Richar d Schelp. “A local density condition for triangles”. In: Discrete Mathematics 127.1 (1994), pp. 153–161

    work page 1994

  12. [12]

    How many edges should be deleted to make a triangle-free graph bipartite

    Paul Erd˝ os, Ervin Gy˝ ori, and Mikl´ os Simonovits. “How many edges should be deleted to make a triangle-free graph bipartite”. In: Sets, graphs and numbers, Colloq. Math. Soc. J´ anos Bolyai. Vol. 60. 1992, pp. 239–263

    work page 1992

  13. [13]

    On application s of Razborov’s flag algebra calculus to extremal 3-graph theory

    Victor Falgas-Ravry and Emil Vaughan. “On application s of Razborov’s flag algebra calculus to extremal 3-graph theory”. In: Combinatorics, Probability and Computing 22(01) (2011), pp. 21–54

    work page 2011

  14. [14]

    On the maximum number of C5’s in a triangle-free graph

    Andrzej Grzesik. “On the maximum number of C5’s in a triangle-free graph”. In: Journal of Combinatorial Theory, Series B 102 (2011), pp. 1061–1066

    work page 2011

  15. [15]

    Minimum numbe r of edges that occur in odd cycles

    Andrzej Grzesik, Ping Hu, and Jan Volec. “Minimum numbe r of edges that occur in odd cycles”. In: Journal of Combinatorial Theory, Series B 137 (2019), pp. 65–103

    work page 2019

  16. [16]

    On the number of pentagons in triangle-free graphs

    Hamed Hatami, Jan Hladk` y, Daniel Kr´ al’, Sergey Norin , and Alexander Razborov. “On the number of pentagons in triangle-free graphs”. In: Journal of Combinatorial Theory, Series A 120.3 (2013), pp. 722–732

    work page 2013

  17. [17]

    Counting flags in triangle-free di- graphs

    Jan Hladk´ y, Daniel Kr´ al, and Sergey Norin. “Counting flags in triangle-free di- graphs”. In: Combinatorica 37.1 (2016), pp. 49–76

    work page 2016

  18. [18]

    An Introduction to Razbo- rov’s Flag Algebra as a Proof System for Extremal Graph Theory

    Gyeongwon Jeong, Seonghun Park, and Hongseok Yang. “An Introduction to Razbo- rov’s Flag Algebra as a Proof System for Extremal Graph Theory”. arXiv: 2601.12741

    work page arXiv

  19. [19]

    Sparse halves in tria ngle-free graphs

    Peter Keevash and Benny Sudakov. “Sparse halves in tria ngle-free graphs”. In: Jour- nal of Combinatorial Theory, Series B 96.4 (2006), pp. 614–620

    work page 2006

  20. [20]

    Semidefinite Pr ogramming and Ramsey Numbers

    Bernard Lidick´ y and Florian Pfender. “Semidefinite Pr ogramming and Ramsey Numbers”. In: SIAM Journal on Discrete Mathematics 35.4 (2021), pp. 2328–2344

    work page 2021

  21. [21]

    Sparse halves in K4-free graphs

    Xizhi Liu and Jie Ma. “Sparse halves in K4-free graphs”. In: Journal of Graph Theory 99.1 (2022), pp. 5–25. 21

    work page 2022

  22. [22]

    Sparse halves in den se triangle-free graphs

    Sergey Norin and Liana Yepremyan. “Sparse halves in den se triangle-free graphs”. In: Journal of Combinatorial Theory, Series B 115 (2015), pp. 1–25

    work page 2015

  23. [23]

    Minimum Number of k-Cliques in Graphs with Bounded Independence Number

    Oleg Pikhurko and Emil Vaughan. “Minimum Number of k-Cliques in Graphs with Bounded Independence Number”. In: Combinatorics, Probability and Computing 22 (2012), pp. 910–934

    work page 2012

  24. [24]

    Flag Algebras

    Alexander Razborov. “Flag Algebras”. In: The Journal of Symbolic Logic 72.4 (2007), pp. 1239–1282

    work page 2007

  25. [25]

    Flag algebras: an interim report

    Alexander Razborov. “Flag algebras: an interim report ”. In: The Mathematics of Paul Erd˝ os II. Springer, 2013, pp. 207–232

    work page 2013

  26. [26]

    More about sparse halves in trian gle-free graphs

    Alexander Razborov. “More about sparse halves in trian gle-free graphs”. In: Sbornik: Mathematics 213.1 (2022), pp. 109–128

    work page 2022

  27. [27]

    On the Caccetta-H¨ aggkvist Conj ecture with Forbidden Sub- graphs

    Alexander Razborov. “On the Caccetta-H¨ aggkvist Conj ecture with Forbidden Sub- graphs”. In: Journal of Graph Theory 74 (2013), pp. 236–248

    work page 2013

  28. [28]

    On the minimal density of triangl es in graphs

    Alexander Razborov. “On the minimal density of triangl es in graphs”. In: Combi- natorics, Probability and Computing 17.4 (2008), pp. 603–618

    work page 2008

  29. [29]

    K4-free graphs have sparse halves

    Christian Reiher. “ K4-free graphs have sparse halves”. In: Bulletin of the London Mathematical Society 55 (2022), pp. 1178–1195

    work page 2022

  30. [30]

    Flag algebras: A first glance

    Marcel de Carli Silva, Fernando M´ ario de Oliveira Filh o, and Cristiane Maria Sato. “Flag algebras: A first glance”. arXiv: 1607.04741

    work page arXiv

  31. [31]

    Note making a K4-free graph bipartite

    Benny Sudakov. “Note making a K4-free graph bipartite”. In: Combinatorica 27.4 (2007), pp. 509–518. 22

    work page 2007