A cut in a graph G is called a bond if both parts of the cut induce connected subgraphs in G, and the bond polytope is the convex hull of all bonds. Computing the maximum weight bond is an NP-hard problem even for planar graphs. However, the problem is solvable in linear time on \((K_5 \setminus e)\) -minor-free graphs, and in more general, on graphs of bounded treewidth, essentially due to clique-sum decomposition into simpler graphs. We show how to obtain the bond polytope of graphs that are 1- or 2-sum of graphs \(G_1\) and \( G_2\) from the bond polytopes of \(G_1,G_2\) . Using this we show that the extension complexity of the bond polytope of \((K_5 \setminus e)\) -minor-free graphs is linear. Prior to this work, a linear size description of the bond polytope was known only for 3-connected planar \((K_5 \setminus e)\) -minor-free graphs, essentially only for wheel graphs. We also describe an elementary linear time algorithm for the Max-Bond problem on \((K_5\setminus e)\) -minor-free graphs. Prior to this work, a linear time algorithm in this setting was known. However, the hidden constant in the big-Oh notation was large because the algorithm relies on the heavy machinery of linear time algorithms for graphs of bounded treewidth, used as a black box.
