Conservative weightings and ear-decompositions of graphs (Q2367443)

An ear-decomposition of a 2-edge-connected graph is defined as a sequence \(G_ 0,G_ 1,\ldots,G_ t=G\) of subgraphs of \(G\) such that \(G_ i\) arises from \(G_{i-1}\) by adding a path \(P_ i\), called ear, with end vertices in \(G_{i-1}\). The minimum number of ears with even length in an ear-decomposition is denoted as \(\varphi(G)\). There is a deep relation between ear-decompositions of \(G\) and the existence of an matching of \(G\). Let \(w:E\to\{-1,1\}\) be an edge-weighting of \(G\) such that \(w(C)\geq 0\) for every circuit \(C\) of \(G\). The maximum number of negative edges in such a weighting is denoted by \(\mu(G)\). The main result of the paper gives the following relation between \(\varphi(G)\) and \(\mu(G)\) \[ \mu(G)=(\varphi(G)+| V|-1)/2 \] where \(| V|\) is the number of vertices in \(G\).