What was already known
Papamanthou and Tollis conjectured MaxSTN would always produce a longest path at least as long as MinSTN on biconnected graphs, based on experiments up to 5,000 vertices.
AI involvement
Papamanthou developed the counterexample interactively with Claude Sonnet 4.6, which wrote the search code. He corrected errors, rejected false candidates and presented the final graph and traces.
The paper identifies the final counterexample as the product of an interactive Claude-led code search, with human supervision and corrections; sole model discovery is not established.
Importance
Refutes a specific graph-algorithm conjecture with a small example.
Limitations
The paper presents the graph and algorithm traces and says the comparison survives tie choices. A complete independent check of the final graph and all tie cases is not documented; earlier generated examples proved false.
Technical verification
The paper gives the finite graph and two worked algorithm traces, but does not document a completed independent check of the final graph, every eligibility step and both tie choices. Earlier false candidates were externally validated and rejected, which does not verify this one.
Human understanding
Papamanthou explains how timestamp order makes MaxSTN branch early and prevents the longer MinSTN chain.
Correction and publication history
Refutes a specific graph-algorithm conjecture with a small example.
Read this published revision