← All problems

Zhao–You–Zhang even-order uniqueness conjecture for minimum net-saturated graphs

Let FF be the net graph, consisting of a triangle together with one distinct degree-one vertex adjacent to each vertex of the triangle. A graph GG is FF-saturated if GG contains no subgraph isomorphic to FF, but G+uvG+uv contains a copy of FF for every nonedge uvuv of GG. For every sufficiently large even integer nn, there is, up to isomorphism, exactly one nn-vertex FF-saturated graph with the minimum possible number of edges.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A November 2026 unrefereed preprint claims the conjecture is false and gives a new classification of the relevant graphs.

The Zhao–You–Zhang conjecture concerns uniqueness of minimum net-saturated graphs of even order.

November 2026 counterexample

Xuanyu Cao and Chunxiang Wang claim the conjecture is disproved: they classify four minimum graphs with 3n/23n/2 edges for every even n≥12n \ge 12, construct further families, and use a ten-vertex example to show the threshold is optimal. This is reported in an unrefereed preprint and remains unverified.

Current status (as of November 2026): The conjecture is claimed disproved by Cao and Wang's preprint, but the classification and counterexample have not been independently assessed.

Sources

Solutions 0

No solutions have been posted yet.