The extremal construction for κ_(L²)(d,k): a four-cell defect and its one-edge repair

Abstract

For a simple graph G let L²(G) be its second iterated line graph, and for integers d ≥ 3 and k ≥ 1 let G(d,k) be the class of simple graphs with δ(G)=d and κ'(G)=k, so that κ_(L²)(d,k)=inf{κ(L²(G)):G ∈ G(d,k)}. A recent preprint of Zou, Xiong, Zhan and Lai evaluates κ_(L²)(d,k)=min{f(d,k), 4d-6} for an explicit four-branch function f. Its upper bound is carried by three constructions, and an unnumbered display in its Section 3 records what those constructions deliver. On the branch (3d-1)/4 ≤ k<d that display reports the value A(d,k)=kd-k²+2k⌊ d/2⌋-⌊ d/2⌋ d, and f(d,k)-A(d,k)=⌊ d/2⌋ (d-2⌊ d/2⌋), which is ⌊ d/2⌋ for odd d: the display reports an upper bound strictly below the value the theorem asserts. We show that, after the cap 4d-6 is applied, the two disagree at exactly four cells, (d,k) ∈ {(3,2),(5,4),(7,5),(7,6)}; that at each of them the graph the display describes has a vertex of degree 2⌊ d/2⌋=d-1 and so lies outside G(d,k); and that adding one edge restores δ=d and makes the same cut count equal f(d,k) exactly. We then supply the upper-bound witnesses that the construction fails to provide at the two smallest cells: two members of G(3,2) whose L² has connectivity exactly 4, one of them a smallest member of the class, and a member of G(5,4) whose 190-vertex L² is cut by 12 vertices. The repaired construction therefore carries, at every cell of the branch, a cut of exactly the size the theorem needs. Every theorem and proposition below is machine-checked in Lean 4, and every connectivity value one of them calls exact is exhaustive over vertex subsets rather than sampled; the remarks, which carry what we did not formalize, say so.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   afe5d2c2c84ec401be2e53f63ecbc103c943b79c45947a883daa0f2e2e64ac5e