Motivated by a problem about totally odd immersions of graphs, we define the odd edge-connectivity λo(u, υ) as the maximum number of edge-disjoint trails of odd length from u to υ. It was recently discovered that λo(u, υ) can be approximated up to a constant multiplicative factor using the usual edge-connectivity between u and v and the minimum value of another parameter that measures “how far from a bipartite graph” the part of the graph around u and v is. In this paper, we formalize this second ingredient and call it the perimeter. We prove that perimeter is a submodular function on the vertex-sets of a graph. Using this fact, we obtain a version of the Gomory–Hu Theorem in which minimum edge-cuts are replaced by sets of minimum perimeter. We construct (in polynomial time) a rooted forest structure, analogous to the Gomory-Hu tree of a graph, which encodes a collection of minimum-perimeter vertex-sets. Although the classical Gomory-Hu Theorem extends to arbitrary symmetric submodular functions, our result is novel and indicates a possibility for further generalizations. These results have significant implications for the study of path and trail systems with parity constraints. We present two such applications: an efficient data structure for storing approximate odd edge-connectivities for all pairs of vertices in a graph, and a rough structure theorem for graphs with no “totally odd” immersion of a large complete graph.

Despite Menger's famous duality between packings and coverings of (u, v)-paths in a graph, there is no duality when we require the paths be odd: a graph with no two edge-disjoint odd (u, v)-paths may need an arbitrarily large number of edges to cover all such paths. In this paper, we study the relaxed problem of packing odd trails. Our main result is an approximate duality for odd trails: if ν(u, v) denotes the maximum number of edge-disjoint (u, v)-trails of odd length in a graph G and τ(u, v) denotes the minimum number of edges that intersect every such trail, then The proof leads to a polynomial-time algorithm to find, for any given k, either k edge-disjoint odd (u, v)-trails or a set of fewer than 8k edges intersecting all odd (u, v)-trails. This yields a constant factor approximation algorithm for the packing number ν(u, v). This result generalizes to the setting of signed graphs and to the setting of group-labelled graphs, in which case “odd length” is replaced by “non-unit product of labels”. The motivation for this result comes from the study of totally odd graph immersions, and our results explain, in particular, why there is an essential difference between the totally odd weak and strong immersions.

A graph is polar if its vertex set can be partitioned into [Formula: see text] and [Formula: see text] in such a way that [Formula: see text] induces a complete multipartite graph and [Formula: see text] induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition [Formula: see text] so that [Formula: see text] induces a [Formula: see text]-free subgraph (i.e., a matching) and [Formula: see text] induces a [Formula: see text]-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an [Formula: see text] time algorithm to solve the stated recognition problem.