![](/files/happy5.png)
The intersection of two perfect matchings
![$ M_1 $](/files/tex/6053a26729abbb4d69de99ccd5976244ef2773c9.png)
![$ M_2 $](/files/tex/b0ecd935059283a5c903e8bbf8faf28490053d61.png)
![$ M_1 \cap M_2 $](/files/tex/15325788d4a123d31609b6e498c31ecaca4b6f19.png)
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.
- \item
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ {\mathbb Z}_2^3 $](/files/tex/b57c731d2b690270c170809d6aff9894eef51fcf.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ C_1,C_2,C_3 $](/files/tex/fae0c4d32358d63b4dbbe72be02580ec28cc4948.png)
![$ C_1 \cup C_2 \cup C_3 = E $](/files/tex/ed7ec7a97bc26db74ea4c14396a4faf5856a4f3b.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ J_1,J_2,J_3 $](/files/tex/7e939933640800aab541082fd3daca755dbde5aa.png)
![$ J_1 \cap J_2 \cap J_3 = \emptyset $](/files/tex/f8cdc4372ffda856cee2514d3834ad69e9f315f1.png)
The last of these statements is interesting, since The Berge Fulkerson Conjecture (if true) implies the following:
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ M_1,M_2,M_3 $](/files/tex/82af2f4bef018aa15c782ece93c7f2288fe49a40.png)
![$ M_1 \cap M_2 \cap M_3= \emptyset $](/files/tex/60bdd82ffe9f6bb6f8f01d8dcd4b0a037c376834.png)
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ J_1,J_2 $](/files/tex/358333f73d81f67bb46c50cb43226a1345f279fa.png)
![$ M $](/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png)
![$ M \cap J_1 \cap J_2 = \emptyset $](/files/tex/105e8cf7e0a05e715c453814cdd0dd94de75b62c.png)
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.