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.

The main arXiv link for this article leads to an updated version of originally published article that bears the assigned DOI. The update concerns Lemma 3.2 and its application in the proof of Lemma 3.3.