2026/08/03 by Chris Ozols · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Bipartite graph #Conjecture #Lemma (botany) #Edge-transitive graph #Graph #Complete bipartite graph #Order (exchange)
paper · doi:10.5281/zenodo.21778700
openalex publication_date 2026/08/03 · openalex created_date 2026/08/04 · openalex updated_date 2026/08/04
Let G be a connected graph on n ≥ 2 vertices. Write f (G) for the maximum order of aninduced forest, b(G) for the maximum order of an induced bipartite subgraph, and p(G) forthe minimum number of vertex-disjoint paths covering V (G). Conjecture 40 of the Writtenon the Wall II (Graffiti.pc) collection asserts f (G) ≥ ⌈(p(G) + b(G) + 1)/2⌉. Introducing thecomplementary parameters τ = n− f (decycling number), o = n− b (odd-cycle transversalnumber), and ℓ= n− p (number of edges in a maximum spanning linear forest), we provethe conjecture is equivalent to the linear inequality ℓ + o ≥ 2τ + 1. For bipartite G this readsℓ ≥ 2τ + 1; we reduce this bipartite case, via an incidence-selection flow model, to two explicitlystated lemmas (Lemma A on forced cores and Lemma B on cycle-erasing descent), provingall of the surrounding structure (a generalized Hall criterion, a rooted forest extension bound,a repaired residual-augmentation flow theorem, and a descent argument) and leaving exactlythose two lemmas open. On the general side we prove, conditional on the bipartite case, thecoefficient-two bound ℓ + 2o ≥ 2τ + 1, and we isolate a single-vertex reduction property (SV )which, together with the bipartite case, implies the full conjecture. Finally we report exhaustivecomputational verification: the conjecture holds for all 1,006,700,565 connected graphs on 11vertices (and all connected graphs on ≤ 10 vertices), with zero violations, under a preregistereddual-engine protocol; SV holds for every connected nonbipartite graph on ≤ 10 vertices.Code, proof documents, ledgers, and verification artifacts: https://github.com/cozuya/wowii-conjecture-40 (v1.0).