← All problems

Mader’s connectivity-keeping tree conjecture and the Luo–Tian–Wu bipartite conjecture

For every positive integer kk and every tree TT with bipartition (X,Y)(X,Y), every kk-connected bipartite graph GG satisfying δ(G)≥k+max⁡{∣X∣,∣Y∣}\delta(G)\ge k+\max\{|X|,|Y|\} contains a subgraph T′≅TT'\cong T such that G−V(T′)G-V(T') is kk-connected.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

Recent papers settle important path-shaped and triangle-free cases, but neither the full tree conjecture nor its bipartite analogue is solved.

Mader’s conjecture, posed in 2012, predicts that sufficiently large minimum degree lets one delete any prescribed tree while preserving kk-connectivity. Luo, Tian, and Wu proposed the bipartite analogue in 2022, with a sharper bound determined by the tree’s bipartition.

Known results

  • Mader proved the connectivity-preserving statement for paths; the general tree case was known for k≤3k\leq 3 but remained open for k≥4k\geq 4.
  • For bipartite graphs, the Luo–Tian–Wu bound is proved for odd-order paths; even-order paths are known with a bound larger by 11 (March 7, 2025 publication).
  • Earlier work handled several special tree families, including caterpillars and spiders for small kk.

October 2026 triangle-free and pendant-path advances

Menghan Ma, Qinghai Liu, Liping Zhang, and Yanmei Hong report optimal or sharpened minimum-degree bounds for paths and all pendant extensions of paths in kk-connected triangle-free graphs, including the conjectured bipartite cases. Related work proves Mader’s conjectured bound for pendant extensions of paths, while Chu, Fujita, Park, and Ryu obtain a broad triangle-free result for arbitrary trees. These are partial advances, not a solution of either full conjecture.

Current status (as of October 2026): The path cases and several restricted tree families are settled, but Mader’s conjecture for arbitrary trees and the full Luo–Tian–Wu bipartite conjecture remain open.

Sources

Solutions 0

No solutions have been posted yet.