% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.63}{25(4)}{2018}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded.
% We recommend these AMS packages:
\usepackage{amsmath,amssymb,epic}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Jan 20, 2017}{Dec 10, 2018}{Dec 21, 2018}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C21, 05C22, 05C38}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% If needed, include a line break (\\) at an appropriate place in the title.
\title{Signed cycle double covers}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

\author{Lingsheng Shi\thanks{Project 11771246 supported by National Natural Science Foundation of China.}\qquad  Zhang Zhang\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Tsinghua University\\[-0.8ex]
\small Beijing, 100084, China\\
\small\tt lshi@math.tsinghua.edu.cn}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
  The cycle double cover conjecture states that every bridgeless graph has a collection of cycles which together cover every edge of the graph exactly twice. A signed graph is a graph with each edge assigned by a positive or a negative sign. In this article, we prove a weak version of this conjecture that is the existence of a signed cycle double cover for all bridgeless graphs. We also show the relationships of the signed cycle double cover and other famous conjectures such as the Tutte flow conjectures and the shortest cycle cover conjecture etc.
\end{abstract}

\section{Introduction}

The Cycle Double Cover Conjecture is a famous conjecture in graph theory. It states that every bridgeless graph has a collection of cycles which together cover every edge of the graph exactly twice. Let $G$ be a graph. A collection of cycles of $G$ is called a {\em cycle cover} if it covers each edge of $G$. A {\em cycle double cover} of $G$ is such a cycle cover of $G$ that each edge lies on exactly two cycles. A graph is called {\em even} if its vertices are all of even degree. A $k$-{\em cycle double cover} of $G$ consists of $k$ even subgraphs of $G$. This conjecture is a folklore (see \cite{BM1}) and it was independently formulated by Szekeres \cite{Sz}, Itai and Rodeh \cite{IR}, and Seymour \cite{Se}. In fact, Szekeres raised this conjecture just for cubic graphs, while Seymour put it in a general case.
\begin{conjecture}\label{SS}{\rm (The Cycle Double Cover Conjecture \cite{Se,Sz})}
Every bridgeless graph has a cycle double cover.
\end{conjecture}
Preissmann \cite{P} and Celmins \cite{C} independently proposed the following stronger conjecture.
\begin{conjecture}\label{CP}{\rm \cite{C,P}}
Every bridgeless graph has a 5-cycle double cover.
\end{conjecture}

The cycle cover problem is closely related to the flow theory. Let $G=(V,E)$ be a graph. An {\em integer flow} of $G$ is an ordered pair $(D,f)$ satisfying
\[\sum_{s(e)=v}f(e)=\sum_{t(e)=v}f(e)\quad\forall v\in V,\]
where $D$ is an orientation of $G$ and $f$ is a function $E\mapsto\mathbb Z$, $s(e)$ denotes the source of $e$ and $t(e)$ denotes the tail of $e$. A {\em nowhere-zero $k$-flow} of $G$ is an integer flow such that $0<|f(e)|<k$ for every edge $e$ of $G$. A {\em group flow} is defined similarly by taking values in an Abelian group instead of $\mathbb Z$. For instance, if a flow takes values in the finite cyclic group $\mathbb Z_k$, then we call it a $\mathbb Z_k$-flow. The {\em support} of a flow $f$, denoted by $supp(f)$, is the set of all the edges $e$ of $G$ with $f(e)\ne 0$. Tutte \cite{T1} found the following relationship of the  integer flow and the group flow.
\begin{theorem}{\rm\cite{T1}}\label{l2}
A  bridgeless graph admits a nowhere-zero $k$-flow if and only if it admits a nowhere-zero group flow with group order $k$.
\end{theorem}
Generalizing the coloring problem of planar graphs, Tutte proposed the following three famous conjectures on integer flows.
\begin{conjecture}{\rm(The Five-Flow Conjecture \cite{T1})}\label{5f}
\hspace{-0.5pt}Every bridgeless graph admits a nowhere-zero 5-flow.
\end{conjecture}
\begin{conjecture}{\rm (The Four-Flow Conjecture \cite{T2})}\label{4f}
Every bridgeless graph containing no subdivision of the Petersen graph admits a nowhere-zero 4-flow.
\end{conjecture}
\begin{conjecture}{\rm (The Three-flow conjecture \cite{BM})}\label{3f}
Every bridgeless graph without 3-edge cuts admits a nowhere-zero 3-flow.
\end{conjecture}
Jaeger \cite{Ja2} and Seymour \cite{Se6} derived two fundamental theorems on integer flows, the Eight-Flow Theorem and the Six-Flow Theorem.
\begin{theorem}{\rm (The Eight-Flow Theorem \cite{Ja2})}
Every bridgeless graph admits a nowhere-zero 8-flow.
\end{theorem}
\begin{theorem}{\rm (The Six-Flow Theorem \cite{Se6})}
Every bridgeless graph admits a nowhere-zero 6-flow.
\end{theorem}
The following relationship of cycle double covers and flows can be found in \cite{Ja}.
\begin{theorem}\label{ccf}{\rm\cite{Ja}}
A graph has a 4-cycle double cover if and only if it admits a nowhere-zero 4-flow.
\end{theorem}
For more backgrounds on cycle covers and flows we refer to the monographs \cite{Z1,Z2}. An ordered pair $(G,\omega )$ is called a {\em weighted graph} if $\omega :E(G)\mapsto\mathbb Z$ is an integer-valued function which is called the {\em weight}. Thus a graph $G$ can be viewed as a special weighted graph $(G,\omega )$ with the constant weight $\omega =1$. Let $G_i=(G,\omega _i)$ be a weighted graph for $i=1,2$. The {\em sum} of $G_1$ and $G_2$ is defined by
\[G_1+G_2=(G,\omega _1+\omega _2),\]
where $(\omega _1+\omega _2)(e)=\omega _1(e)+\omega _2(e)$ for each $e \in E(G)$. The {\em difference} of $G_1$ and $G_2$ is defined by
\[G_1-G_2=(G,\omega _1-\omega _2),\]
where $(\omega _1-\omega _2)(e)=\omega _1(e)-\omega _2(e)$ for each $e \in E(G)$.

A {\em general signed graph} $(G,\omega )$ is such a weighted graph that $\omega (e)\in\{0,\pm 1\}$ for all $e\in E(G)$. This generalizes the notion of {\em signed graph} which edges are allowed to take only two values $\pm 1$. Since the support of a general signed graph is just its signed subgraph, we simply call it a signed graph without confusion. Thus a subgraph $H$ of $G$ can be viewed as a signed graph $(G,\omega _H)$, where $\omega _H(e)=1$ for $e\in E(H)$ and $\omega _H(e)=0$ for $e\in E(G)\setminus E(H)$. A signed graph $(G, \omega )$ is {\em even} if $\sum _{u\in N(v)}\omega (uv)$ is even for all $v\in V(G)$, where $N(v)$ denotes the neighborhood of $v$ in $G$. An edge $e$ of $G$ is called {\em negative} if $\omega (e)=-1$. The number of negative edges in $(G,\omega )$ is $|\omega ^{-1}(-1)|$.

A collection of even signed graphs $\{G_1,G_2,\ldots,G_t\}$ of $G$ is called a {\em signed cycle double cover} of $G$ if it satisfies
\[\sum_{i=1}^{t} \omega_{G_i}(e)=2,\quad\forall e \in E(G).\]
A $k$-{\em signed cycle double cover} consists of $k$ even signed graphs. Let $\Gamma $ be a signed cycle double cover. The total number of  negative edges of $\Gamma $, denoted by $\nu (\Gamma )$, is defined by
$$\nu (\Gamma )=\sum_{H\in\Gamma }\left |\omega _H^{-1}(-1)\right |.$$

Though Conjectures~\ref{SS} and~\ref{CP} are widely open and it is well known that the Petersen graph has no 4-cycle double cover, we establish the following weak version by replacing cycles with signed cycles. This is analogous in some sense to a result of Seymour \cite{Se1} who proved the weak signed versions of the Berge-Fulkerson Conjecture \cite{F,Se1} about double covers by perfect matchings and the Tutte Four-Flow Conjecture in its dual coloring form for cubic graphs.
\begin{theorem}\label{t1}
Every bridgeless graph of order $n$ and size $m$ has a 4-signed cycle double cover $\Gamma $ with $\nu (\Gamma )\le\min\{n/3,m/9\}$.
\end{theorem}
M\' a\v cajov\' a and \v Skoviera \cite[Theorem 1.1]{MS} proved that every bridgeless cubic graph has a Fano coloring which uses at most six different lines. Moreover, if at most six points are used in the Fano coloring, then there is a nowhere-zero 4-flow. This is a consequence of the following theorem which is stated in the flow form instead of coloring.
\begin{theorem}\label{cf}
A graph admits a nowhere-zero 4-flow if and only if it admits a nonsurjective nowhere-zero $\mathbb Z_2^3$-flow.
\end{theorem}
Though the bound in Theorem~\ref{t1} is hardly improved (see Corollary~\ref{c2}), it may not be sharp because of the following result.
\begin{theorem}\label{t2}
There exist infinitely many graphs of size $m$ such that all 4-signed cycle double covers have at least $m/15$ negative edges.
\end{theorem}
In view of Theorems~\ref{t1} and~\ref{t2}, we propose the following conjecture.
\begin{conjecture}\label{sc}
Every bridgeless graph of size $m$ has a 4-signed cycle double cover with at most $m/15$ negative edges.
\end{conjecture}
Note that Theorem~\ref{t1} implies Conjecture~\ref{sc} for all bridgeless graphs of order $n$ and size $m\ge 5n$. We prove Theorems \ref{t1}, \ref{cf}, and \ref{t2} in Section 2 and finish with a discussion in Section 3 on the relationship of the signed cycle double cover and other conjectures, such as the Shortest Cycle Cover Conjecture and the Tarsi Conjecture on the shortest 3-cycle covers etc.

\section{Proofs of main results}
The proof of Theorem \ref{t1} is based on the Six-Flow Theorem and the Eight-Flow Theorem. It is to construct directly a signed cycle double cover which differs from the approach of Seymour \cite{Se1} who made signed covers by perfect matchings indirectly from multicolorings. The idea of our proof is as follows.

A 6-flow induces a $\mathbb Z_3\times\mathbb Z_2$-flow. The support $C$ of the $\mathbb Z_2$-flow can be taken as a disjoint union of circuits with size at most $n$. The $\mathbb Z_3$-flow induces a 3-cycle double cover of its support. All even subgraphs form an Abelian group under the operation of symmetric difference, and all even weighted graphs also form an additive group, though all even signed graphs do not. Applying the three operations of addition, subtraction, and symmetric difference to $C$ and the three cycles, and taking care of the weights of all edges, we get two 4-signed cycle double covers with disjoint sets of negative edges $E_1$ and $E_2$ appearing only on the support $C$. The three disjoint sets $E_1, E_2$, and $E(C)\setminus E_1\cup E_2$ form a partition of all edges of $C$. But both $E_1$ and $E_2$ might be of size greater than $n/3$. In this case, we make a new $\mathbb Z_3$-flow by pivoting the $\mathbb Z_2$-flow so that one of the two sets $E_1$ and $E_2$ changes to the set $E(C)\setminus E_1\cup E_2$ which is of size at most $n/3$.

An 8-flow induces a $\mathbb Z_2^3$-flow that in turn induces a partition of all edges into 7 subsets. The three supports of the $\mathbb Z_2$-flows all induce even subgraphs. Taking symmetric differences of the three supports yields four new even subgraphs. The key observation is that every one of the 7 subsets of edges is covered exactly 4 times by the 7 even subgraphs and the corresponding 4 even subgraphs form a signed cycle double cover.  Bermond et al. \cite{BJJ} observed that the $\mathbb Z_2^3$-flow can be taken so that one of the supports is large with at least $2m/3$ edges. Three of the 7 subsets of edges are disjoint with the largest support, so we can take the smallest one as the set of negative edges which size turns out be at most $m/9$.

\begin{proof}[Proof of Theorem~\ref{t1}] 
Let $G$ be a bridgeless graph of order $n$ and size $m$. We first show that $G$ has a 4-signed cycle double cover with $\nu\le n/3$. By Theorem~\ref{l2} and the Six-Flow Theorem, the graph $G$ admits a nowhere-zero $\mathbb Z_3\times \mathbb Z_2$-flow, say $(f,g)$. Let $C$ be the even subgraph of $G$ induced by $supp(g)$. By the proof of the Six-Flow Theorem \cite{Se6}, the flow $g$ can be selected such that $C$ is a union of disjoint circuits with $|E(C)|\le n$. Note that $f$ is a nowhere-zero $\mathbb Z_3$-flow on $supp(f)$ which can be turned to a nowhere-zero 3-flow by Theorem~\ref{l2}. Since a 3-flow can be viewed as a 4-flow, the support of $f$ has a 3-cycle double cover, denoted by $\{C_{01},C_{02},C_{03}\}$. Indeed, if the pair $(g_1,g_2$) is a nowhere-zero $\mathbb Z _2^2$-flow on $supp(f)$, then let $C_{01}$ and $C_{02}$ be the even subgraphs induced by $supp(g_1)$ and $supp(g_2)$ respectively, and let $C_{03}=C_{01}\triangle C_{02}$ be the subgraph of $G$ induced by the symmetric difference $E(C_{01})\triangle E(C_{02})$.

Let $f_i=f+ig$ (mod 3) for $i=1,2$. As for the flow $f$, both $supp(f_1)$ and $supp(f_2)$ also have 3-cycle double covers, denoted by $\{C_{11},C_{12},C_{13}\}$ and $\{C_{21},C_{22},C_{23}\}$, respectively. One can easily verify that
\[C_1=C\triangle C_{11} + C\triangle C_{12} + C\triangle C_{13} - C_{01} - C_{02} - C_{03}\]
is a signed even graph of $G$. Indeed, let $e$ be an edge of $G$ and we go through the following three cases.

\medskip
Case 1. $f(e)=0$, $g(e)\ne 0$.

\medskip
In this case, we have $e\in E(C)\cap supp(f_1)\setminus supp(f)$, and then $e$ is in exactly two of $\{C_{11},C_{12},C_{13}\}$ and none of $\{C_{01},C_{02},C_{03}\}$. Thus $e$ is in only one of $$\{C\triangle C_{11}, C\triangle C_{12}, C\triangle C_{13}\}$$ and $\omega _{C_1}(e)=1$.

\medskip
Case 2. $f(e)\ne 0$, $g(e)=0$.

\medskip
In this case, we have $e\in supp(f)\cap supp(f_1)\setminus E(C)$, and then $e$ is in exactly two of $\{C_{i1},C_{i2},C_{i3}\}$ for $i=0,1$. Thus $e$ is in exactly two of $\{C\triangle C_{11}, C\triangle C_{12}, C\triangle C_{13}\}$ and $\omega _{C_1}(e)=0$.

\medskip
Case 3. $f(e)\ne 0$, $g(e)\ne 0$.

\medskip
If $f(e)=1$, then $e\in E(C)\cap supp(f)\cap supp(f_1)$ and thus $e$ is in exactly two of $\{C_{i1},C_{i2},C_{i3}\}$ for $i=0,1$ and in only one of $\{C\triangle C_{11}, C\triangle C_{12}, C\triangle C_{13}\}$ which implies that $\omega _{C_1}(e)=-1$. If $f(e)=2$, then $e\in E(C)\cap supp(f)\setminus supp(f_1)$ and thus $e$ is in exactly two of $\{C_{01},C_{02},C_{03}\}$ and in all of $\{C\triangle C_{11}, C\triangle C_{12}, C\triangle C_{13}\}$ which implies that $\omega _{C_1}(e)=1$.

\medskip
The even signed graph $C_1$ together with the three even subgraphs $C\triangle C_{21}$, $C\triangle C_{22}$, $C\triangle C_{23}$ forms a 4-signed cycle double cover of $G$, denoted by $\Gamma _1$, which is shown in Table~\ref{G1}.
\begin{table}
\begin{center}
\begin{tabular}{cc|ccccc|c}
$g(e)$ & $f(e)$ & $f_1(e)$ & $f_2(e)$ & $\omega _C(e)$ & $\omega _{C_1}(e)$ & $\omega _{C\triangle C_{21}+C\triangle C_{22}+C\triangle C_{23}}(e)$ & $\displaystyle\sum _{H\in\Gamma _1}\omega _H(e)$\\ \hline
0 & 1 & 1 & 1 & 0 & 0 & 2 & 2\\
1 & 0 & 1 & 2 & 1 & 1 & 1 & 2\\
1 & 1 & 2 & 0 & 1 & $-1$ & 3 & 2\\
1 & 2 & 0 & 1 & 1 & 1 & 1 & 2
\end{tabular}
\caption{The 4-signed cycle double cover $\Gamma _1$.}\label{G1}
\end{center}
\end{table}
Similarly, let
\[ C_2=C\triangle C_{21} + C\triangle C_{22} + C\triangle C_{23} - C_{01} - C_{02} - C_{03},\]
which together with the three even subgraphs $C\triangle C_{11}$, $C\triangle C_{12}$, $C\triangle C_{13}$ forms another 4-signed cycle double cover of $G$, denoted by $\Gamma _2$, see Table~\ref{G2}.
\begin{table}
\begin{center}
\begin{tabular}{cc|ccccc|c}
$g(e)$ & $f(e)$ & $f_1(e)$ & $f_2(e)$ & $\omega _C(e)$ & $\omega _{C_2}(e)$ & $\omega _{C\triangle C_{11}+C\triangle C_{12}+C\triangle C_{13}}(e)$ & $\displaystyle\sum _{H\in\Gamma _2}\omega _H(e)$\\ \hline
0 & 1 & 1 & 1 & 0 & 0 & 2 & 2\\
1 & 0 & 1 & 2 & 1 & 1 & 1 & 2\\
1 & 1 & 2 & 0 & 1 & 1 & 1 & 2\\
1 & 2 & 0 & 1 & 1 & $-1$ & 3 & 2
\end{tabular}
\caption{The 4-signed cycle double cover $\Gamma _2$.}\label{G2}
\end{center}
\end{table}

Note that only in Case 3 can negative edges occur in $C_1$ or $C_2$ and all such negative edges are on $C$. Indeed, an edge $e$ in $C_1$ is negative if and only if $f(e)=g(e)=1$ and an edge $e'$ in $C_2$ is negative if and only if $f(e')=2$ and $g(e')=1$.

Let $E_i=f^{-1}(i)\cap E(C)$ for $i=0,1,2$. Clearly, $\nu (\Gamma _i)=|\omega ^{-1}_{C_i}(-1)|=|E_i|$ for $i=1,2$. If $|E_0|\ge n/3$, then let $\Gamma $ be one of $\{\Gamma _1,\Gamma _2\}$ with smaller value $\nu $ and thus $\nu (\Gamma )=\min\{\nu (\Gamma _1),\nu (\Gamma _2)\}=\min\{|E_1|,|E_2|\}\le |E(C)\setminus E_0|/3\le n/3$.

If $|E_1|\ge n/3$, then let $f'=f-g$ (mod 3). Note that $f'$ is still a $\mathbb{Z}_3$-flow and the difference between $f$ and $f'$ can only occur on $C$. Thus $(f',g)$ is also a nowhere-zero $\mathbb{Z}_3\times \mathbb{Z}_2$-flow of $G$. Similarly, let $E'_i=f'^{-1}(i)\cap E(C)$ for $i=0,1,2$. Clearly, $E'_0=E_1$, $E'_1=E_2$, and $E'_2=E_0$. As above, $G$ has a 4-signed cycle double cover with $\nu =\min\{|E_1'|,|E_2'|\}=\min\{|E_0|,|E_2|\}\le n/3$.

If $|E_2|\ge n/3$, then let $f''=f+g$ (mod 3). As the above argument, $(f'',g)$ is also a nowhere-zero $\mathbb{Z}_3\times \mathbb{Z}_2$-flow of $G$. Also let $E''_i=f''^{-1}(i)\cap E(C)$ for $i=0,1,2$. Clearly,  $E''_0=E_2$, $E''_1=E_0$, and $E''_2=E_1$. Thus $G$ also has a 4-signed cycle double cover with $\nu =\min\{|E''_1|,|E''_2|\}=\min\{|E_0|,|E_1|\}\le n/3$. This completes the proof of the first part.

\medskip
Next we show that $G$ has a 4-signed cycle double cover with $\nu\le m/9$. By Theorem~\ref{l2} and the Eight-Flow Theorem, the graph $G$ admits a nowhere-zero $\mathbb{Z}_2^3$-flow, say $f=(f_1,f_2,f_3)$. Let $C_i$ be the even subgraph of $G$ induced by $supp(f_i)$ for $i=1,2,3$. As observed by Bermond et al. \cite{BJJ}, the flow $f$ can be selected such that $|E(C_1)|\ge 2m/3$. It is obvious that $C_1$, $C_2$, and $C_3$ form a cycle cover of $G$, i.e., $E(G)=\cup_{i=1}^{3}E(C_i)$. We define seven subsets of $E(G)$ as follows,
\[E_{i_1i_2i_3}=\{e\in E(G): f(e)=(i_1,i_2,i_3)\},\mbox{ where } (i_1,i_2,i_3)\in\mathbb{Z}_2^3\setminus\{\mathbf 0\}.\]
Since $f$ is a nowhere-zero $\mathbb{Z}_2^3$-flow of $G$, the seven subsets defined above form a partition of $E(G)$.

We claim that $G$ has a 4-signed cycle double cover with $\nu =\min\{|E_{i_1i_2i_3}|: (i_1,i_2,i_3)\in\mathbb Z_2^3\setminus\{\mathbf 0\}\}$. To see this, we define an incidence matrix $M$ in the following way. The rows of $M$ correspond to the seven subsets of edges listed in the following order:
\[E_{100},~E_{110},~E_{111},~E_{101},~E_{010},~E_{011},~E_{001}.\]
The columns of $M$ correspond to the seven even subgraphs of $G$ listed in the following order:
\[C_1,~C_2,~C_3,~C_1\triangle C_2,~C_1\triangle C_3,~C_2\triangle C_3,~C_1\triangle C_2\triangle C_3.\]
Let $M=(a_{ij})_{7\times 7}$, where $a_{ij}=1$ if the $i$th subset is a subset of edges in the $j$th even subgraph, otherwise $a_{ij}=0$ for $i,j=1,2,\ldots,7$. Explicitly,
\[M=\left(
  \begin{array}{ccccccc}
    1 & 0 & 0 & 1 & 1 & 0 & 1 \\
    1 & 1 & 0 & 0 & 1 & 1 & 0 \\
    1 & 1 & 1 & 0 & 0 & 0 & 1 \\
    1 & 0 & 1 & 1 & 0 & 1 & 0 \\
    0 & 1 & 0 & 1 & 0 & 1 & 1 \\
    0 & 1 & 1 & 1 & 1 & 0 & 0 \\
    0 & 0 & 1 & 0 & 1 & 1 & 1 \\
  \end{array}
\right).\]
It is easily verified that $M$ has the following property:

\medskip
{\em Each row of $M$ has exactly 4 non-zero entries and each of the other six rows has exactly 2 non-zero entries at the 4 columns corresponding to such 4 non-zero entries of that row.}

\medskip
Let $E^*$ be one of the seven subsets of edges with minimum size. Without loss of generality, we may assume that $E^*=E_{001}$, i.e., the 7th subset. Select the four even subgraphs corresponding to the four non-zero entries of the 7th row, i.e., $C_3$, $C_1\triangle C_3$, $C_2\triangle C_3$, and $C_1\triangle C_2\triangle C_3$. By the above property of $M$, these four even subgraphs form a cycle cover of $G$ which covers every edge of $E_{001}$ 4 times and all the other edges twice. Replacing all edges of $E_{001}$ in $C_3$ by negative edges, we get a 4-signed cycle double cover with $\nu =|E^*|\le\min\{|E_{010}|,|E_{011}|,|E_{001}|\}\le (m-|E(C_1)|)/3\le m/9$. This completes the proof of the second part.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{cf}] 
Theorem~\ref{l2} implies that a graph admitting a nowhere-zero 4-flow has a nowhere-zero $\mathbb Z_2^2$-flow which can obviously be viewed as a nonsurjective $\mathbb Z_2^3$-flow. Conversely, if $G$ admits a nonsurjective nowhere-zero $\mathbb Z_2^3$-flow, then $G$ has a 4-signed cycle double cover without negative edges by the proof of Theorem~\ref{t1}, i.e., $G$ has a 4-cycle double cover, which is equivalent to the fact that $G$ admits a nowhere-zero 4-flow by Theorem~\ref{ccf}.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{t2}] 
Consider the Petersen graph $P$ of order 10 and size 15. Since $P$ fails to admit a nowhere-zero 4-flow, it has no 4-cycle double cover by Theorem~\ref{ccf}. Thus every 4-signed cycle double cover of $P$ has at least one negative edge. In fact, the lower bound can be achieved, see Fig.~\ref{peter} for instance: The dotted edge is negative and the first even signed graph together with other three even subgraphs shown in Fig.~\ref{peter} form a 4-signed cycle double cover of $P$ with only one negative edge. For a natural number $k$, a $k$-{\em subdivision} of a graph is obtained from the graph by subdividing each edge exactly $k$ times. It is easy to see that a $k$-subdivision of the Petersen graph also has a corresponding 4-signed cycle double cover with only $k$ negative edges.
\begin{figure}
\begin{picture}(450,100)
\put(50,20){\circle*{4}}
\put(100,20){\circle*{4}}
\put(36,65){\circle*{4}}
\put(114,65){\circle*{4}}
\put(75,94){\circle*{4}}
\put(75,76){\circle*{4}}
\put(56,60){\circle*{4}}
\put(94,60){\circle*{4}}
\put(61,38){\circle*{4}}
\put(89,38){\circle*{4}}
\drawline(50,20)(36,65)(75,94)(114,65)(100,20)(89,38)(75,76)(61,38)
{\thicklines\dottedline{2}(50,20)(61,38)}
\put(150,20){\circle*{4}}
\put(200,20){\circle*{4}}
\put(136,65){\circle*{4}}
\put(214,65){\circle*{4}}
\put(175,94){\circle*{4}}
\put(175,76){\circle*{4}}
\put(156,60){\circle*{4}}
\put(194,60){\circle*{4}}
\put(161,38){\circle*{4}}
\put(189,38){\circle*{4}}
\drawline(150,20)(161,38)(194,60)(156,60)(189,38)(200,20)(150,20)
\put(250,20){\circle*{4}}
\put(300,20){\circle*{4}}
\put(236,65){\circle*{4}}
\put(314,65){\circle*{4}}
\put(275,94){\circle*{4}}
\put(275,76){\circle*{4}}
\put(256,60){\circle*{4}}
\put(294,60){\circle*{4}}
\put(261,38){\circle*{4}}
\put(289,38){\circle*{4}}
\drawline(250,20)(236,65)(256,60)(294,60)(314,65)(275,94)(275,76)(261,38)(250,20)
\put(350,20){\circle*{4}}
\put(400,20){\circle*{4}}
\put(336,65){\circle*{4}}
\put(414,65){\circle*{4}}
\put(375,94){\circle*{4}}
\put(375,76){\circle*{4}}
\put(356,60){\circle*{4}}
\put(394,60){\circle*{4}}
\put(361,38){\circle*{4}}
\put(389,38){\circle*{4}}
\drawline(350,20)(361,38)(394,60)(414,65)(400,20)(350,20)
\drawline(336,65)(375,94)(375,76)(389,38)(356,60)(336,65)
\end{picture}
\vskip -0.4cm\caption{A 4-signed cycle double cover of the Petersen graph.}\label{peter}
\end{figure}
As in \cite{JT}, one can construct a more general graph of size $m$ such that its 4-signed cycle double covers all have at least $m/15$ negative edges. Denote by $P'$ the graph obtained from the Petersen graph $P$ in the following way: Delete a vertex $v$ of $P$ and the three edges $vv_1$, $vv_2$, and $vv_3$ which are incident with $v$, and add three new vertices $u_1, u_2, u_3$ which are called the {\em arms} of $P'$ and three new edges $u_iv_i$ for $i=1,2,3$, see Fig.~\ref{pp}.
\begin{figure}
\begin{center}
\begin{picture}(140,130)
\put(50,20){\circle*{4}}
\put(100,20){\circle*{4}}
\put(36,65){\circle*{4}}
\put(114,65){\circle*{4}}
\put(75,104){\circle*{4}}
\put(75,76){\circle*{4}}
\put(56,60){\circle*{4}}
\put(94,60){\circle*{4}}
\put(61,38){\circle*{4}}
\put(89,38){\circle*{4}}
\put(36,104){\circle*{4}}
\put(114,104){\circle*{4}}
\drawline(75,76)(61,38)(94,60)(56,60)(89,38)(75,76)
\drawline(36,104)(36,65)(50,20)(100,20)(114,65)(114,104)
\drawline(36,65)(56,60)(89,38)(100,20)(114,65)(94,60)(61,38)(50,20)
\drawline(75,104)(75,76)
\put(32,110){$u_1$}
\put(70,110){$u_2$}
\put(110,110){$u_3$}
\put(22,65){$v_1$}
\put(62,76){$v_2$}
\put(120,65){$v_3$}
\end{picture}
\end{center}
\vskip -0.8cm\caption{The graph $P'$ obtained from the Petersen graph.}\label{pp}
\end{figure}
Take a bridgeless cubic graph $G$ of order $n$. A graph denoted by $G\otimes P$, is constructed from $G$ and $P$ as follows: Replace every vertex $v$ of $G$ by a copy of $P'$, denoted by $P'_v$. For every edge $uv$ of $G$, select an arm of $P'_u$ which is not used and such a arm of $P'_v$, and identify these two arms forming a new vertex of degree two. It is clear that $G\otimes P$ is also bridgeless. Select a 4-signed cycle double cover of $G\otimes P$ arbitrarily (the existence of such a cover is ensured by Theorem~\ref{t1}), say $\Gamma =\{ C_1,C_2,C_3,C_4\}$. For every subgraph $P'_v$ of $G\otimes P$, identifying its three arms results in a graph isomorphic to $P$, and the collection $\Gamma _v=\{ C_1\cap P'_v,\ldots,C_4\cap P'_v\}$ corresponds to a 4-signed cycle double cover of the graph. Thus $\nu (\Gamma _v)\ge 1$ and $$\nu(\Gamma)=\sum_{v\in V(G)}\nu(\Gamma_v)\ge n=|E(G\otimes P)|/15,$$ since the graph $G\otimes P$ has exactly $15n$ edges.
\end{proof}

\section{Related conjectures}

In this section, we relate the signed cycle double covers to the short cycle covers. The {\em length} of a cycle cover is the sum of the lengths of all its cycles. A cycle cover of a graph $G$ with the shortest total length is called the {\em shortest cycle cover} of $G$ and the length is denoted by $SCC(G)$. Especially, the length of the shortest 3-cycle cover of $G$ is denoted by $SCC_3(G)$. Jaeger (see \cite{MRTZ}) made the following general conjecture on the shortest cycle covers.
\begin{conjecture}\label{at}\rm{(The Shortest Cycle Cover Conjecture)}
Every bridgeless graph of size $m$ has a cycle cover with total length at most $7m/5$.
\end{conjecture}
The bound in Conjecture~\ref{at}, if true, is sharp by the Petersen graph.
Jamshy and Tarsi \cite{JT} showed that Conjecture \ref{at} implies the Cycle Double Cover Conjecture. It is well known that every shortest cycle cover of the Petersen graph consists of 4 even subgraphs, see \cite{IR,JT}. Moreover, Fan and Raspaud \cite{FR} pointed out that there are infinitely many bridgeless graphs of size $m$ that have no 3-cycle cover with total length less than $22m/15$. Tarsi (see \cite{Z1}) proposed the following conjecture which is weaker than the Berge-Fulkerson Conjecture, see \cite{FR}.
\begin{conjecture}\label{t}{\rm\cite{Z1}}
Every bridgeless graph of size $m$ has a $3$-cycle cover with length at most $22m/15$.
\end{conjecture}
Alon and Tarsi \cite{AT} and Bermond, Jackson, and Jaeger \cite{BJJ} independently gave a general upper bound, showing $SCC_3(G)\le 5m/3$ for a bridgeless graph $G$ of size $m$ by applying the Six-Flow Theorem and the Eight-Flow Theorem respectively. Moreover, if $G$ is cubic, then Jackson \cite{J} gave a better bound by $SCC_3(G)\le 64m/39\approx 1.641m$, Fan \cite{F2} later improved this bound to $SCC_3(G)\le 44m/27\approx 1.629m$, and Kr\' al et al. \cite{KN} further improved to $SCC_3(G)\le 34m/21\approx 1.619m$. Kaiser et al. \cite{KK} extended the Fan bound $SCC_3(G)\le 44m/27$ from bridgeless cubic graphs to all bridgeless graphs with minimum degree at least 3.

The short cycle covers also relate to the flow theory. Jamshy et al. \cite{JRT} proved that the Tutte Five-Flow Conjecture (Conjecture~\ref{5f}) implies the bound $SCC_3(G)\le 8m/5$ for all bridgeless graphs $G$ of size $m$. Fan \cite{F2} proved that the Tutte Three-Flow Conjecture (Conjecture~\ref{3f}) implies that $SCC_3(G)\le 92m/57\approx 1.614m$. We establish the relationship of the short cycle covers and the signed cycle covers in the following theorem.

\begin{theorem}\label{mn}
The following statements hold for all graphs $G$ of size $m$.
\begin{enumerate}
\item If $G$ has a 4-signed cycle double cover with $\nu $ negative edges, then $G$ has a 3-cycle cover of length at most $3(m+\nu )/2$.
\item If $G$ has a 3-cycle cover of length $l$, then $G$ has a 4-signed cycle double cover with at most $(l-m)/5$ negative edges.
\end{enumerate}
\end{theorem}
\begin{proof}
(1) Let $\Gamma $ be a 4-signed cycle double cover of $G$ with $\nu $ negative edges. Replacing all the negative edges in $\Gamma $ by normal edges, we get a cycle cover, denoted by $\{C_1,C_2,C_3,C_4\}$, which covers all the negative edges of $\Gamma $ exactly 4 times and the other edges exactly twice. The total length of this cycle cover is $4\nu+2(m-\nu)=2m+2\nu$. Without loss of generality, we assume that $C_1$ has the maximum length among the cycle cover, and then the other three even subgraphs $C_2$, $C_3$, and $C_4$ make up a cycle cover with length no more than $3(m+\nu)/2$.

(2) Let $\{C_1,C_2,C_3\}$ be a 3-cycle cover of $G$ with length $l$. Clearly, $G$ admits a nowhere-zero $\mathbb Z_2^3$-flow, say $f=(f_1,f_2,f_3)$, such that $C_i$ is induced by $supp(f_i)$ for $i=1,2,3$. Following the notation such as the edge subsets $E_{i_1i_2i_3}$ in the proof of Theorem~\ref{t1}, we have
\[l=\sum_{i=1}^{3}|E(C_{i})|=|E(G)|+|E_{110}|+|E_{101}|+|E_{011}|+2|E_{111}|.\]
Thus $|E_{110}|+|E_{101}|+|E_{011}|+2|E_{111}|=l-m$. As in the proof of Theorem~\ref{t1}, the graph $G$ has a 4-signed cycle double cover with $\nu\le\min\{|E_{110}|,|E_{101}|,|E_{011}|,|E_{111}|\}\le (l-m)/5$.
\end{proof}

Theorems~\ref{t1} and~\ref{mn} readily imply the bound of Alon-Tarsi and Bermond-Jackson-Jaeger that $SCC_3(G)\le 5m/3$ for every bridgeless graph $G$ of size $m$. Theorem~\ref{mn} also implies the following results.
\begin{corollary}\label{c1}
Conjecture~\ref{sc} implies that every bridgeless graph of size $m$ has a 3-cycle cover with length at most $8m/5$.
\end{corollary}
\begin{corollary}\label{c2}
Conjecture~\ref{t} implies that every bridgeless graph of size $m$ has a 4-signed cycle double cover with at most $7m/75$ negative edges.
\end{corollary}
Corollary~\ref{c1}, compared with the result of Jamshy et al. \cite{JRT}, indicates that it might be hard to prove Conjecture~\ref{sc}, and Corollary~\ref{c2} shows that the bound in Theorem~\ref{t1} might also be hardly improved since the bound $7m/75$ is slightly better than $m/9$.

\begin{thebibliography}{99}
\bibitem{AT} N. Alon and M. Tarsi. \newblock Covering multigraphs by simple circuits. \newblock \emph{Algebraic Discrete Methods}, 6:345--350, 1985.
\bibitem{BJJ} J. Bermond, B. Jackson, and F. Jaeger. \newblock Shortest coverings of graphs with cycles.  \newblock \emph{J. Combin. Theory, Ser. B}, 35:297--308, 1983.
\bibitem{BM1} J. A. Bondy and U. S. R. Murty. \newblock Graph Theory. \newblock Springer, 2008.
\bibitem{BM} J. A. Bondy and U. S. R. Murty. \newblock Graph Theory with Applications. \newblock Macmillan, London, 1976.
\bibitem{C} U. A. Celmins. \newblock On cubic graphs that do not have an edge 3-coloring. \newblock Ph.D. thesis, University of Waterloo, Ontario, Canada, 1984.
\bibitem{F2} G. Fan. \newblock Shortest cycle covers of cubic graphs. \newblock \emph{J. Graph Theory}, 18(2):131--141, 1994.
\bibitem{FR} G. Fan and A. Raspaud. \newblock Fulkerson's conjecture and circuits covers. \newblock \emph{J. Combin. Theory, Ser. B}, 61:133--138, 1994.
\bibitem{F} D. R. Fulkerson. \newblock Blocking and anti-blocking pairs of polyhedra. \newblock \emph{Math. Programming}, 1:168--194, 1971.
\bibitem{IR} A. Itai and M. Rodeh. \newblock Covering a graph by circuits. \newblock In\emph{Automata, Languages and Programming}, volume 62 of \emph{Lecture Notes in Computer Science}, pages 289--299. Berlin: Springer-Verlag, 1978.
\bibitem{J} B. Jackson. \newblock Shortest circuit covers of cubic graphs. \newblock \emph{J. Combin. Theory, Ser. B}, 60:299--307, 1994.
\bibitem{Ja} F. Jaeger. \newblock Flows and generalized coloring theorems in graphs. \newblock \emph{J. Combin. Theory, Ser. B}, 26:205--216, 1979.
\bibitem{Ja2}  F. Jaeger. \newblock On nowhere-zero flows in multigraphs. \newblock \emph{Proceedings of the Fifth British Combinatorial Conference} 1975, \emph{Congr. Numer.}, 15:373--378, 1975.
\bibitem{JRT}  U. Jamshy, A. Raspaud, and M. Tarsi. \newblock Short circuit covers for regular matroids with nowhere-zero 5-flows. \newblock \emph{J. Combin. Theory, Ser. B}, 43:354--357, 1987.
\bibitem{JT}  U. Jamshy and M. Tarsi. \newblock Shortest cycle covers and the cycle double cover conjecture. \newblock  \emph{J. Combin. Theory, Ser. B}, 56:197--204, 1992.
\bibitem{KK}  T. Kaiser, D. Kr\' al, B. Lidick\' y, and P. Nejedl\' y. \newblock Short cycle covers of graphs with minimum degree three. \newblock \emph{SIAM J. Discrete Math.}, 24:330--355, 2010.
\bibitem{KN} D. Kr\' al, P. Nejedl\' y, and R. \v S\' amal. \newblock Short cycle covers of cubic graphs.  \newblock \emph{KAM-DIMATIA Series} 2008--846, Department of Applied Mathematics, Charles University, Prague, Czech, 2008.
\bibitem{MRTZ} E. M\' a\v cajov\' a, A. Raspaud, M. Tarsi, and X.-D. Zhu. \newblock Short cycle covers of graphs and nowhere-zero flows. \newblock \emph{J. Graph Theory}, 68:340--348, 2011.
\bibitem{MS} E. M\' a\v cajov\' a and M. \v Skoviera. \newblock Fano colourings of cubic graphs and the Fulkerson conjecture. \newblock \emph{Theoretical Computer Science}, 349:112--120, 2005.
\bibitem{P} M. Preissmann. \newblock Sur les colorations des ar\^ etes des graphes cubiques. \newblock Th\` ese de Doctorat de $3^{eme}$, Ph.D. thesis, Universit\' e de Grenoble, France, 1981.
\bibitem{Se6}  P. D. Seymour. \newblock Nowhere-zero 6-flows. \newblock \emph{J. Combin. Theory, Ser. B}, 30:130--135, 1981.
\bibitem{Se1} P. D. Seymour. \newblock On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. \newblock \emph{Proc. London Math. Soc.}, 38(3):423--460, 1979.
\bibitem{Se}  P. D. Seymour. \newblock Sums of circuits. \newblock In \emph{Graph Theory and Related Topics}, (J. A. Bondy and U. S. R. Murty, eds.) pages 341--355, Academic Press, New York, 1979.
\bibitem{Sz}  G. Szekeres. \newblock Polyhedral decompositions of cubic graphs. \newblock \emph{Bull. Austral. Math. Soc.}, 8:367--387, 1973.
\bibitem{T1}  W. T. Tutte. \newblock A contribution to the theory of chromatic polynomials. \newblock \emph{Canadian J. Math.}, 6:80--91, 1954.
\bibitem{T2}  W. T. Tutte. \newblock On the algebraic theory of graph colorings. \newblock \emph{J. Combin. Theory}, 1:15--50, 1966.
\bibitem{Z1}  C. Zhang. \newblock Circuit Double Covers of Graphs. \newblock Cambridge University Press, 2012.
\bibitem{Z2}  C. Zhang. \newblock Integer flows and cycle covers of graphs. \newblock Marcel Dekker, New York, 1997.
\end{thebibliography}

\end{document}