Generative Structural Theory v1.141 — A Budget-Two Obstruction to Two-Step Reachability in Example P
Can one minimally strongly connected directed graph be transformed into another in two steps if each step may delete at most two edges? This preprint answers that question for the two leaf lifts W and W′ in Example P of v1.140. The lifts have 21 vertices, and their union A₀ = W ∪ W′ contains 33 edges. Each step may add edges from A₀. The intermediate graph must be minimally strongly connected on the same vertex set. Version 1.140 ruled out two specific forms of intermediate graph. Here its form is unrestricted. Theorem N shows that exactly three intermediate graphs meet the first-step deletion budget: W itself and two graphs obtained from W by replacing one edge. Each of the three contains exactly three edges absent from W′. Reaching W′ in the second step therefore requires three deletions in every case. Corollary N6 concludes that there is no two-step connection from W to W′ inside A₀ under deletion budget two. The proof uses explicit directed cuts and walks. The verification appendix reports an exhaustive enumeration for Example P that gives the same result. Of the 1,344 edge sets satisfying both deletion budgets, 108 are strongly connected and none is minimally strongly connected. Whether a longer connection exists inside A₀ under the same budget remains open.
Authors
- Koji Okino (ORCID: https://orcid.org/0009-0003-9273-9813)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24283491
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint