A tight relation between series--parallel graphs and bipartite distance hereditary graphs

Bandelt and Mulder’s structural characterization of bipartite distance hereditary graphsasserts that such graphs can be built inductively starting from a single vertex and by re-peatedly adding either pendant vertices or twins (i.e., vertices with the same neighborhoodas an existing one). Dirac and Duffin’s structural characterization of 2–connected series–parallel graphs asserts that such graphs can be built inductively starting from a single edgeby adding either edges in series or in parallel. In this paper we give an elementary proofthat the two constructions are the same construction when bipartite graphs are viewed asthe fundamental graphs of a graphic matroid. We then apply the result to re-prove knownresults concerning bipartite distance hereditary graphs and series–parallel graphs and toprovide a new class of polynomially-solvable instances for the integer multi-commodityflow of maximum value.