Decomposing a signed graph into rooted circuits

Min-max theorems play an important role in combinatorics and optimization. Abstractly speaking, a min-max theorem says that the minimum of a parameter is equal to the maximum of the dual parameter. Prominent specific min-max theorems include the max-flow min-cut theorem, Kőnig’s theorem and Menger’s theorem. For example, Menger’s theorem asserts that the maximum number of edge-disjoint paths between vertices $u$ and $v$ in a graph is equal to the minimum size of an edge-cut separating $u$ and $v$.

Motivated by problems concerning vertex-minors of graphs, the author of this paper considers the following problem: given an Eulerian graph $G$, a vertex $b$ and a set $S$ of edges, what is the maximum number of closed trails passing through $b$ such that each trail contains an odd number of edges from $S$ and the trails partition the edge set of $G$? Note that this quantity stays unchanged whenever for a fixed vertex $v$, all edges incident with $v$ and not present in $S$ are added to $S$ and those already present are removed. We refer to this operation as a local shifting.

An upper bound on the number of trails in the problem stated above can be obtained as follows. Let $X$ be a set of vertices of $G$ that contains $b$. Observe that each trail passing through $b$ that has an odd number of edges from $S$ contains an edge from $S$ with both end vertices in $X$ or leaves and so reenters the set $X$ (and therefore contains two edges between a vertex in $X$ and a vertex not in $X$). This yields an upper bound on the number of trails. However, for example, if one of the components of $G\setminus X$ is joined by two edges to $X$ and the number of edges from $S$ among those contained in the component and the two edges to $X$ is even, the above upper bound can be decreased by one. This is an example of a bad component of $G\setminus X$. The main result of the paper asserts that the maximum number of trails is equal to the minimum of the aforementioned upper bound minus the number of bad components of $G\setminus X$, taken over all sets $X$ and all local shiftings. As a corollary, a proof of the following conjecture of Máčajová and Škoviera is obtained: the edges of every $2\ell$-regular graph with an odd number of vertices can be split into $\ell$ closed trails passing through the same vertex and each having an odd number of edges.