Mader's connectivity-keeping tree conjecture
Mader's connectivity-keeping tree conjecture
Throughout, graphs are finite, simple, and undirected; and are positive integers, the order of a graph is its number of vertices, and denotes its connectivity. A graph is -connected when . A tree has order when it has vertices.
Mader's conjecture. For any tree of order , every -connected graph with minimum degree
contains a subtree such that
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 and remains open for ; 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
Sign in to submit a solution.
No solutions have been posted yet.