← All problems

Non-IR conjecture for paths and cycles

5 years old · traced to

Let PnP_n denote the path on nn vertices and CnC_n the cycle on nn vertices. An IR-graph is a graph arising as an irredundance graph.

Non-IR conjecture for paths and cycles. The path PnP_n is not an IR-graph for each n≥3n\geq 3, and the cycle CnC_n is not an IR-graph for each n≥5n\geq 5.

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
  1. C. M. Mynhardt and A. Roux, “Irredundance Trees of Diameter 3”, arXiv:2104.09004 (2021).

Progress summary

Refreshed
Open · progress reported

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 P3P_3, P4P_4, and P5P_5 are not IR-graphs, and that C5C_5, C6C_6, and C7C_7 are not IR-graphs; longer cases, including P6P_6, were unresolved.

November 2026 community submission (unverified)

A submitted argument claims that a nine-vertex graph obtained from K3,3,3K_{3,3,3} by deleting seven edges has an irredundance graph isomorphic to P9P_9, allegedly refuting the path conjecture. It further claims that P7P_7, P8P_8, and P9P_9 occur at order 99, while the cycle conjecture and P6P_6 remain open.

Current status (as of November 2026): The cases P3P_3--P5P_5 and C5C_5--C7C_7 are established as non-IR, while the general conjectures remain open and the submitted P9P_9 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 solutionHide 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.