The maximum removable matching conjecture in k-connected graphs

Less than 1 year old · traced to

Let GG be a kk-connected graph on nn vertices with minimum degree δ(G)≥k+2\delta(G)\ge k+2. A matching is kk-removable when deleting its edges leaves a kk-connected graph. The maximum removable matching conjecture. The graph GG contains a kk-removable matching of size min⁡{⌊n/2⌋,δ(G)}\min\{\lfloor n/2\rfloor,\delta(G)\}. This conjecture concerns the largest matching size permitted by the order of the graph and the minimum-degree bound. The supplied context gives no resolution or partial status for it, so it remains open.

References

Primary source

Hengzhe Li, Mingming Zhou, Shinya Fujita and Yaping Mao, “From Halin's Edge Removability to Matching Removability in k-Connected Graphs”, arXiv:2605.24035 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.