Open Problem Garden

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.

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.