The bend-number of K_{4,5} is three
The bend-number b(G) of a graph G is the least k such that G is the edge-intersectiongraph of paths in a rectangular grid, each with at most k bends. Heldt, Knauer and Ueckerdt(2014) proved b(Km,m) = ⌈m/2⌉ and gave bounds for Km,n. For m = 4 these results giveb(K4,4) = 2 and b(K4,n) = 3 for 6 ≤ n ≤ 8, but they leave the case K4,5 open. We show thatK4,5 has no 2-bend representation, so b(K4,5) = 3 and K4,n is a 2-bend graph exactly whenn ≤ 4. The proof reduces the question to a 27 × 27 grid by an order-preserving compression ofcoordinates. It then refutes a SAT encoding of the finite question, and an independent checkerverifies the solver’s LRAT proof. Cross-checks with a second, independently written encodingare in progress. As a by-product, the open MIPLIB 2017 instance neos-3603137-hoteo, whichasks for a 2-bend representation of K4,5 on an 8 × 8 grid, is infeasible. All programs, formulasand verification logs are released with this note.
Authors
- Stylianos Iordanis (ORCID: https://orcid.org/0000-0002-1217-5591)
Institutions
- National Technical University of Athens (GR)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24390485
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint