Koch-Narayan Conjecture 1

For a bipartite graph without isolated vertices and with a unique minimum dominating set, does the proposed function $m(n, \gamma)$ bound the number of edges whenever $\gamma \ge 2$ and $n \ge 3\gamma$ ? A $13$ -vertex bipartite graph with $22$ edges exceeds the conjectured maximum of $21$ .

Result: Disproved
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Extremal graph theory
Posed by: Koch & Narayan
Year posed: 2025
Years open: 1y
Solved: 2026-06-12
Model: Demonstrandum multi-agent pipeline
Vendor: —
Collaborators: —
Verification: Unreviewed
Publication: Announced
Significance: 5 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What the AI did

Found by the Demonstrandum multi-agent pipeline; every refutation ships a finite certificate, a mutation-tested checker, and an independent clean-room recomputation.

Verification

Exact certificate verified by two independently written checkers; public artifacts repository. Not externally refereed.

Source

Demonstrandum artifacts repository (RESULTS.md)

Koch-Narayan Conjecture 1

What the AI did

Verification

Source

Discussion