For every finite graph G with order n=|V(G)|, size m=|E(G)|, and maximum degree Delta=Delta(G), does the identifying vertex cover number of G satisfy the upper-bound inequality conjectured by Henning and Yeo in terms of n, m, and Delta?

Henning–Yeo conjecture on identifying vertex covers

Henning and Yeo proposed the identifying-vertex-cover inequality in 2012. Their conjecture is now disproved by an explicit family of connected counterexamples.

Known results

Henning and Yeo, 2012: the inequality holds for regular graphs.
Henning and Yeo, 2012: it holds for maximum degree $2$ and $3$ .
For maximum degree $2$ , equality occurs precisely when every component is $P_3$ or $C_5$ .

August 2026 counterexamples

Yufeng Wang gives a two-parameter counterexample family, arbitrarily large connected examples, and an exhaustive minimum-order check. The construction also rules out rounding or fixed additive corrections as simple repairs of the conjectured inequality.

Current status (as of August 2026): The conjectured inequality is settled false by Wang’s arXiv preprint; the preprint’s asymptotic normalized-gap statement remains independently unchecked.

Henning–Yeo conjecture on identifying vertex covers

Primary source

Additional references

Progress summary

Solutions 0