Mader's connectivity-keeping tree conjecture

From papers

Throughout, graphs are finite, simple, and undirected; \k\k and \m\m are positive integers, the order of a graph is its number of vertices, and κ(G)\kappa(G) denotes its connectivity. A graph is \k\k-connected when κ(G)k\kappa(G)\geq k. A tree has order \m\m when it has \m\m vertices.

Mader's conjecture. For any tree \T\T of order \m\m, every \k\k-connected graph \G\G with minimum degree

δ(G)3k2+m1\delta(G)\geq \left\lfloor\frac{3k}{2}\right\rfloor+m-1

contains a subtree \TT\T'\cong T such that

κ(GV(T))k.\kappa(G-V(T'))\geq k.

Mader proved the corresponding assertion for a path, and later obtained a weaker quadratic minimum-degree bound for arbitrary trees. The conjecture is known for \k3\k\leq 3 and remains open for \k4\k\geq 4; a linear minimum-degree sufficient condition is known.

Progress summary

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

Sources & referencesView supporting material

Primary source

Hojin Chu, Shinya Fujita, Boram Park and Homoon Ryu, “Connectivity keeping trees in triangle-free graphs”, arXiv:2511.06622 (2025).

Additional references

6 papers in this index state this conjecture (2011–2025). The statement above is taken from the most recent of them; the others are arXiv:2012.04816, arXiv:1808.00455, arXiv:1606.05507, arXiv:1401.2696, arXiv:1101.2357.

Solutions 0

No solutions have been posted yet.