Here’s the solution for Petersen graph:

Up to isomorphisms, there’s only 1 solution for Petersen graph.

There are 2 types of vertices:

- blue — (we’ll call them
) — each pair of edges, that goes through this vertex in every cycle, is oriented in the same direction*oriented* - black — (we’ll call them
) — same pairs are oriented differently in different cycles*non-oriented*

Here’s the solution for one of Blanuša snarks (todo: probably it’s the first Blanuša snark)

- Black and violet edges are
*rich*. Every edge is covered 4 times, and now we take a look at the neighboring edges. If we have 4 different possibilities, then the edge is.*rich* - Red and orange edges are
— there are only 2 possibilities which occur twice in the covering.**poor**

Black and red edges constitute *2-factors*, violet and orange edges constitute *perfect matchings*.

*Oriented* vs *non-oriented* — the story is about o6c4c (oriented 6-cycle 4-cover). *Rich* vs *poor* — the story is about general 6c4c.

This classification of edges is connected to Petersen coloring: if the 6c4c solution comes from Petersen coloring, we’ll get the ordinary definition of rich (all 5 colors in the neighborhood) and poor edges (only 3 colors).

Computational verification shows, that every (cyclically 4-edge connected with girth at least 5) snark with up to (and including) 30 vertices has at least 1 oriented Berge-Fulkerson solution. We’ll state this as a **conjecture** (oriented Berge-Fulkerson conjecture): every bridgeless cubic graph has an oriented 6-cycle 4-cover (these cycles are called 2-factors, because they are incident to every vertex in the graph) (the complement to these cycles are perfect matchings).

So this construction is also a clarification (and errata) to the 2 pages at Open Problems Garden:

- http://www.openproblemgarden.org/op/m_n_cycle_covers (The orientable eight cycle four cover conjecture)
- http://www.openproblemgarden.org/op/cycle_double_cover_conjecture (The oriented cycle four cover conjecture)

#### Some notation

*s0*— number of*circuits (*is a connected cycle; there are 12 in the solution for Petersen graph)**circuit***s1*— number of*rich*edges (15 for Petersen graph)*s2*— half of the number of perfect matchings with even number of*rich*edges (so in general it’s equal to 0, 1, 2 or 3) (0 for Petersen graph)*or*— number of*oriented*vertices*t1*— number of*poor*edges which connect*oriented*with*oriented*vertex- (
*t2*— number of*poor*edges which connect*oriented*with*non-oriented*vertex) (not used) *t3*— number of*rich*edges which connect*oriented*with*non-oriented*vertex*t4*— number of*rich*edges which connect*non-oriented*with*non-oriented*vertex*total_poor_comps*— number of connected components of*poor*edges*odd_poor_comps_2-factors*— number of 2-factors with odd number of connected components of*poor*edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (likewise we can define things as, e. g.,*odd_rich_comps_2-factors,*where we count 2-factors with odd number of connected components of*rich*edges; or*odd_poor_comps_matchings*, where we count perfect matchings with odd number of connected components of*poor*edges)*odd_poor_2-factors*— number of 2-factors with odd number of*poor*edges (so it can be one of 0, 1, 2, 3, 4, 5 or 6) (so we don’t count connected components of edges, just edges themselves) (so,*s2*is same as*even_rich_matchings*/ 2)*nz-mod-k*— nowhere-zero mod-*k*flow solution (which maybe doesn’t exist), built with 2-factors having weights from*0*to*k — 1*and using modular arithmetics (we are interested in*k = 5*and*k = 6*)

## General case

These statements are easy to prove:

*or*has same parity as*t3**or*has same parity in all possible orientations of fixed 6c4c solution

Some not yet proven computational observations (checked on snarks with small number of vertices, I will later specify these numbers and decipher every notation):

- There’s always at least one dominating circuit which goes through all oriented vertices
- If
*or = 0,*then*s2 = 3* - If
*or = 0,*then*s0*has same parity as*s1* - There are no solutions with
*or = 1* - There are no solutions with 16 rich edges
- There are never less than 15 rich edges for snarks
- if
*t1 + t3 < 9,*then*s0 + s1 + s2*is odd - There are no solutions with
*t1 + t3 = 7* *odd_poor_comps_2-factors*is even,*odd_rich_comps_2-factors*is even,*odd_poor_comps_matching*is even (but*odd_rich_comps_matching*may have any parity) (if we count not components but just the edges then this becomes obvious)- if we have o6c4c,
*nz-mod5*and don’t have*nz-mod6,*then*or > 2*and*s0*is even - if
*total_poor_comps = 1,*then*s1 + s2*is odd;

sometimes patterns start to break only when number of vertices is huge (usually works upto 26 and breaks on 28 vertices):

- upto 26: if
*total_poor_comps = 1,*and if the solution is orientable (so we have o6c4c) then*s0*is even; breaks on 28.05g611

## Case of splitting into 2 separate 6cdcs

If the 6c4c solution comes from Petersen coloring, then its also possible to divide the circuits into 2 separate 6-cycle double covers (we’ll denote this as ** 2x6cdcs**). If we have a general 6c4c solution, then in case we have such decomposition:

- it’s easy to show that we can have only 1 such decomposition up to circuit isomorphisms

Also we have some unproven statements for this case:

*total_poor_comps > 1**odd_poor_2-factors = 0**s2*is either 0 or 3- if the solution is orientable (so we have o6c4c) then
*s0*is even*or + s1*is even (or same as saying that*t4*is even)

## Q&A

**Q**: Are there any other graphs with 0 poor edges?

**A**: Yes, later I’ll show here an example

**Q**: Are there graphs with or = 0 and with splitting into 2x6cdcs?

**A**: TODO

…