Tree-compositions and orientations

A tree-composition is a tree-like family that serves to describe the obstacles to kk-edge-connected orientability of mixed graphs. Here we derive a structural result on tree-compositions that gives rise to a simple algorithm for computing an obstacle when the orientation does not exist.As another application, we show a min–max theorem on the minimal in-degree of a given node set in a kk-edge-connected orientation of an undirected graph. This min–max formula can be simplified in the special case of k=1k=1.