On the mixed connectivity conjecture of Beineke and Harary - Sebastian S. Johann; Sven O. Krumke; Manuel Streicher (Annals of Operations Research, 2023)
The conjecture of Beineke and Harary states that for any two vertices which can be separated by k vertices and l edges for l≥1but neither by~ k vertices and l-1edges nor k-1vertices and l edges there are~ k+ledge-disjoint paths connecting these two vertices of which k+1are internally disjoint.In this paper we prove this conjecture for~ l=2and every k∈N.We utilize this result to prove that the conjecture holds for all graphs of treewidth at most 3 and all k and l .
Keywords: 000; Mixed connectivity; Mixed cut; Menger; Graph theory