Non-IR conjecture for paths and cycles
Let denote the path on vertices and the cycle on vertices. An IR-graph is a graph arising as an irredundance graph.
Non-IR conjecture for paths and cycles. The path is not an IR-graph for each , and the cycle is not an IR-graph for each .
These are open problems concerning which graphs can occur as irredundance graphs. They are stated together in the paper's list of conjectures and open problems and are attributed there to Mynhardt (2019).
References
- C. M. Mynhardt and A. Roux, “Irredundance Trees of Diameter 3”, arXiv:2104.09004 (2021).
Progress summary
A reader-submitted, unverified construction claims that the path conjecture is false, while the cycle conjecture remains open.
The conjectures, attributed to Mynhardt (2019), assert that no path with at least three vertices and no cycle with at least five vertices is an IR-graph.
Known results
The cited paper proves that , , and are not IR-graphs, and that , , and are not IR-graphs; longer cases, including , were unresolved.
November 2026 community submission (unverified)
A submitted argument claims that a nine-vertex graph obtained from by deleting seven edges has an irredundance graph isomorphic to , allegedly refuting the path conjecture. It further claims that , , and occur at order , while the cycle conjecture and remain open.
Current status (as of November 2026): The cases -- and -- are established as non-IR, while the general conjectures remain open and the submitted counterexample is unverified.
Sources
Solutions 1
part (i) of the conjecture (paths) is false: P_9 is an IR-graph; computationally 9 is the minimum order of a graph whose IR-graph is a path of order >= 3 and P_7, P_8, P_9 occur at order 9; part (ii) (cycles) and P_6 remain openSee full solution
The paper exhibits a nine-vertex, twenty-edge graph, obtained from K_(3,3,3) by deleting seven edges. Its upper irredundance number is three, and its nine maximum irredundant sets form P_9 under the required vertex-exchange adjacency. Two small tables provide a hand-checkable proof, accompanied by the Lean certificate. This refutes the path part of the conjecture. The cycle part and the case P_6 remain open in this work; the bounded exhaustive-search claims are distinct from the formalized counterexample.
Result and scope: part (i) of the conjecture (paths) is false: P_9 is an IR-graph; computationally 9 is the minimum order of a graph whose IR-graph is a path of order >= 3 and P_7, P_8, P_9 occur at order 9; part (ii) (cycles) and P_6 remain open
Complete proof and verification sources: The path P_9 is an IR-graph: a nine-vertex counterexample to the Mynhardt-Roux non-IR conjecture for paths · PDF.
The paper page includes the supplementary proof-source JSON attachment and extract_sources.py, which reconstruct the archived proof and verification sources. The linked paper gives the complete rigorous argument and specifies exactly which statements are formalized.
This is an AI-assisted research preprint. Internal review is not external journal peer review; bounded prior-art searches do not certify worldwide priority. See the paper for the source, interpretation, formalization, and trust limitations.