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 oriented) — each pair of edges, that goes through this vertex in every cycle, is oriented in the same direction
- black — (we’ll call them non-oriented) — same pairs are oriented differently in different cycles
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 poor — there are only 2 possibilities which occur twice in the covering.
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)
- s0 — number of circuits (circuit is a connected cycle; there are 12 in the solution for Petersen graph)
- 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)
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; if the solution is orientable (so we have o6c4c) then s0 is even
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: 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?