On the size of two minimal linkages

We prove that for any two positive integers k 1 and k 2 , if G is a graph, S 1 , T 1 , S 2 , T 2 are vertex-subsets of G , and G is edge-minimal with respect to the condition that for i = 1 , 2 there are k i disjoint paths of G between S i and T i , then G contains at most 12 k 1 k 2 vertices of degree at least three. This bound is optimal up to a constant factor, as a k 1 × k 2 -grid G shows. The degree-3 treewidth sparsifier theorem, proved by Chekuri and Chuzhoy (2015), states that for any graph G of treewidth at least k , there is a subcubic subgraph of G that has treewidth Ω ( k / poly log ⁡ k ) and contains O ( k 4 ) vertices of degree three. Our result, together with their proof techniques, reduces the bound O ( k 4 ) in this theorem to O ( k 2 ) , solving their conjecture.