Fan's Conjecture: Signed Circuit 6-Covers of Coverable Signed Graphs

Fan's conjecture asserts that every coverable signed graph admits a signed circuit 6-cover: a family of signed circuits — balanced circuits and barbells — in which every edge appears in exactly six members. It is the signed-graph analogue of the classical theorem that every bridgeless graph has a circuit $k$ -cover for every even $k\ge 4$ , and the constant 6 is the smallest possible, since for each $k\le 5$ infinitely many coverable signed graphs admit no signed circuit $k$ -cover. The conjecture has been verified for signed eulerian graphs, for signed graphs whose bridgeless blocks are eulerian, and — in Lu–Luo–Miao–Zhang (2025) — for signed $K_4$ -minor-free graphs, where 6 is tight. As of August 2026 the conjecture remains open for arbitrary coverable signed graphs.

Background

Circuit covers of ordinary graphs. A circuit of a graph is a connected 2-regular subgraph. A family $\mathcal{F}$ of circuits is a circuit cover of a graph $G$ if every edge lies in at least one member of $\mathcal{F}$ , and a circuit $k$ -cover if every edge lies in exactly $k$ members. Bermond, Jackson and Jaeger (1983) proved that every bridgeless graph has a circuit $4$ -cover, and Fan (1992) proved that every bridgeless graph has a circuit $6$ -cover; together these yield a circuit $k$ -cover for every even integer $k\ge 4$ . The remaining case $k=2$ is the classical circuit double cover conjecture, which remains open.

Signed graphs. A signed graph $(G,\sigma)$ is a graph together with a signature $\sigma:E(G)\to\{+1,-1\}$ assigning a sign to each edge; graphs in this area are finite and may have loops and parallel edges. A circuit is balanced if it contains an even number of negative edges and unbalanced otherwise. Switching at a vertex flips the signs of all edges incident with it and does not change which circuits are balanced. The circuits of signed-graph theory are the signed circuits: a signed circuit is either a balanced circuit or a barbell, meaning the union of two unbalanced circuits and a (possibly trivial) path, called the barbell-path, that meets the two circuits only at its ends. Signed circuits are exactly the minimal dependent sets of the signed-graphic matroid (the frame matroid) associated with $(G,\sigma)$ , so signed circuit covers are the natural matroidal generalization of circuit covers of ordinary graphs.

Covers and coverability. A signed circuit cover of $(G,\sigma)$ is a family of signed circuits covering every edge at least once, and a signed circuit $k$ -cover requires every edge to be covered exactly $k$ times. A signed graph is coverable if it has a signed circuit cover at all. Coverability admits several equivalent characterizations: a connected signed graph is coverable if and only if its negativeness $\epsilon(G)$ — the minimum number of negative edges over all switchings — is not equal to $1$ and no cut edge $b$ has a balanced component of $G-b$ (Proposition 2.2 of Lu–Luo–Miao–Zhang); equivalently $(G,\sigma)$ admits a nowhere-zero integer flow (an assignment of a nonzero integer to each edge, conserved at every vertex; in signed-graph flow theory a negative edge reverses the effective direction of flow); equivalently its signed-graphic matroid has no coloops, a coloop being an edge that belongs to no signed circuit of $(G,\sigma)$ . Unlike the ordinary case, where any bridge trivially prevents a circuit cover, coverable signed graphs may contain bridges, which barbells can traverse along their barbell-paths.

The signed $k$ -cover problem. For ordinary bridgeless graphs, circuit $k$ -covers exist for every even $k\ge 4$ . For signed graphs the situation is provably worse: for every integer $k\le 5$ there are infinitely many coverable signed graphs with no signed circuit $k$ -cover, and there exist signed eulerian graphs — graphs in which every vertex has even degree — that admit a nowhere-zero $2$ -flow yet have no signed circuit $1$ -cover. Hence $k=6$ is the smallest value that could possibly be universal for signed graphs, and Genghua Fan conjectured exactly that: every coverable signed graph has a signed circuit $6$ -cover. The conjecture appears in print in Chen–Fan (2021) and Bao–Chen–Fan (2021). It has been verified for three families: signed eulerian graphs (Bao–Chen–Fan 2021); signed graphs whose bridgeless blocks — the maximal 2-edge-connected subgraphs, i.e. the components left after deleting all bridges — are all eulerian (Chen–Fan 2021); and signed $K_4$ -minor-free graphs, i.e. graphs with no $K_4$ (complete graph on four vertices) minor, a class containing all series-parallel and outerplanar graphs (Lu–Luo–Miao–Zhang 2025). Lu–Luo–Miao–Zhang also show that 6 is best possible even within this last class, since a coverable signed graph with four degree-3 vertices spanning one balanced and one unbalanced $2$ -circuit — a $2$ -circuit being a pair of parallel edges joining the same two vertices — admits no signed circuit $k$ -cover for any $k\in[1,5]$ .

Problem Statement

Must every coverable signed graph have a signed circuit $6$ -cover?

Concretely: let $(G,\sigma)$ be a finite signed graph (loops and parallel edges allowed) that is coverable, i.e. it admits at least one family of signed circuits (balanced circuits and barbells) covering every edge; equivalently, for connected $G$ , its negativeness $\epsilon(G)\ne 1$ and no cut edge $b$ of $G$ has a balanced component of $G-b$ ; equivalently, the signed-graphic matroid of $(G,\sigma)$ has no coloops. Is there always a family $\mathcal{F}$ of signed circuits of $(G,\sigma)$ such that every edge of $G$ lies in exactly $6$ members of $\mathcal{F}$ ?

The expected answer is yes — this is Fan's conjecture, the signed-graph analogue of the classical theorem that every bridgeless ordinary graph has a circuit $k$ -cover for every even $k\ge 4$ . The constant 6 cannot be lowered, since for every $k\le 5$ there are infinitely many coverable signed graphs with no signed circuit $k$ -cover. The question is open for arbitrary coverable signed graphs: the cases of signed eulerian graphs, of signed graphs whose bridgeless blocks are eulerian, and of signed $K_4$ -minor-free graphs are already settled affirmatively, so the open content concerns precisely the coverable signed graphs with at least one non-eulerian bridgeless block and at least one bridgeless block containing a $K_4$ minor.

References

You Lu, Rong Luo, Zhengke Miao, Cun-Quan Zhang. Signed Circuit 6-Covers of Signed K4-Minor-Free Graphs. The Electronic Journal of Combinatorics 32(2) (2025), #P2.5. DOI: 10.37236/12572. https://doi.org/10.37236/12572 (arXiv preprint: arXiv:2310.17098, https://arxiv.org/abs/2310.17098)
Jing Chen, Genghua Fan. Circuit k-covers of signed graphs. Discrete Applied Mathematics 294 (2021) 41–54. DOI: 10.1016/j.dam.2021.01.024. https://doi.org/10.1016/j.dam.2021.01.024
Bo Bao, Rong Chen, Genghua Fan. Circuit Covers of Signed Eulerian Graphs. The Electronic Journal of Combinatorics 28(1) (2021), #P1.14. DOI: 10.37236/9084. https://doi.org/10.37236/9084
Edita Máčajová, André Raspaud, Edita Rollová, Martin Škoviera. Circuit Covers of Signed Graphs. Journal of Graph Theory 81 (2016) 120–133. DOI: 10.1002/jgt.21866. https://doi.org/10.1002/jgt.21866
Genghua Fan. Integer flows and cycle covers. Journal of Combinatorial Theory, Series B 54 (1992) 113–122. DOI: 10.1016/0095-8956(92)90069-A. https://doi.org/10.1016/0095-8956(92)90069-A
J.-C. Bermond, B. Jackson, F. Jaeger. Shortest coverings of graphs with cycles. Journal of Combinatorial Theory, Series B 35 (1983) 297–308. DOI: 10.1016/0095-8956(83)90056-4. https://doi.org/10.1016/0095-8956(83)90056-4