Importance: Medium ✭✭
 Author(s): Macajova, Edita Skoviera, Martin
 Subject: Graph Theory » Basic Graph Theory » » Matchings
 Keywords: cubic nowhere-zero flow perfect matching
 Posted by: mdevos on: August 30th, 2007
Conjecture   Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Let be a bridgeless cubic graph. A binary cycle (henceforth called cycle) is a set so that every vertex of has even degree (equivalently, a cycle is any member of the binary cycle space). A postman join is a set so that is a cycle. Note that since is cubic, every perfect matching is a postman join. Next we state a well-known theorem of Jaeger in three equivalent forms.

Theorem  (Jaeger's 8-flow theorem)
\item has a nowhere-zero flow in the group . \item has three cycles so that . \item has three postman joins so that .

The last of these statements is interesting, since The Berge Fulkerson Conjecture (if true) implies the following:

Conjecture has three perfect matchings so that .

So, we know that has three postman joins with empty intersection, and it is conjectured that may be chosen so that each is a perfect matching, but now we see two statements in between the theorem and the conjecture. Namely, is it true that may be chosen so that one is a perfect matching? or two? The first of these was solved recently.

Theorem  (Macajova, Skoviera) has two postman sets and one perfect matching so that The second of these asks for two perfect matchings and one postman join so that . It is an easy exercise to show that a set contains a postman join if an only if has nonempty intersection with every odd edge-cut. Therefore, finding two perfect matchings and one postman join with empty common intersection is precisely equivalent to the conjecture at the start of this page - find two perfect matchings whose intersection contains no odd edge-cut.

## Bibliography

* Edita Macajova, Martin Skoviera, Fano colourings of cubic graphs and the Fulkerson conjecture. Theoret. Comput. Sci. 349 (2005), no. 1, 112--120. MathSciNet

* indicates original appearance(s) of problem.