The Berge-Fulkerson conjecture

Discussion

This conjecture is due to Berge and Fulkerson, and appears first in [F] (see [S79b]). If $ G $ is 3- edge-colorable , then we may choose three perfect matchings $ M_1,M_2,M_3 $ so that every edge is in exactly one. Taking each of these twice gives us 6 perfect matchings with the properties described above. Thus, the above conjecture holds trivially for 3-edge-colorable graphs. There do exist bridgeless cubic graphs which are not 3-edge-colorable (for instance the Petersen graph ), but the above conjecture asserts that every such graph is close to being 3-edge-colorable. Definition: An $ r $ -graph is an $ r $ - regular graph $ G $ on an even number of vertices with the property that every edge-cut which separates $ V(G) $ into two sets of odd cardinality has size at least $ r $ . Observe that a cubic graph is a 3-graph if and only if it has no bridge. If G is an $ r $ -regular graph which has an $ r $ -edge-coloring, then every color class is a perfect matching, so $ |V(G)| $ must be even, and every color must appear in every edge-cut which separates $ V(G) $ into two sets of odd size, so every edge-cut of this form must have size at least $ r $ . Thus, every $ r $ -edge-colorable $ r $ -regular graph is an $ r $ -graph. In a sense, we may view the $ r $ -graphs as the $ r $ -regular graphs which have the obvious necessary conditions to be $ r $ -edge-colorable. Seymour [S79b] defined $ r $ -graphs and offered the following generalization of the Berge-Fulkerson conjecture. Conjecture (The generalized Berge-Fulkerson conjecture (Seymour)) Let $ G $ be an $ r $ -graph. Then there exist $ 2r $ perfect matchings $ M_1,\ldots,M_{2r} $ of $ G $ with the property that every edge of $ G $ is contained in exactly two of $ M_1,\ldots,M_{2r} $ . More generally, for a graph $ G=(V,E) $ , one may consider the vector space of real numbers indexed by $ E $ . We associate every perfect matching $ M $ with its characteristic vector. In this context, the Berge-Fulkerson conjecture asserts that for every 3-graph, the vector which is identically 1 may be written as a half-integer combination of perfect matchings. Edmonds matching polytope theorem [E] gives a complete characterization of what vectors in $ {\mathbb R}^E $ which can be written as a nonnegative real combination of perfect matchings. A particular consequence of this theorem is that the vector which is identically 1 can be written as a nonnegative rational combination of perfect matchings if G is an $ r $ -graph. It follows from this that for every $ r $ -graph $ G $ , there is a list of perfect matchings $ M_1,\ldots,M_{kr} $ so that every edge is contained in exactly $ k $ of them. Unfortunately, the particular $ k $ depends on the graph. The following weak version of the Berge-Fulkerson conjecture asserts that this dependence is inessential. Conjecture (the weak Berge-Fulkerson conjecture) There exists a positive integer $ k $ with the following property. Every 3-graph $ G $ has a list of $ 3k $ perfect matchings such that every edge of $ G $ is contained in exactly $ k $ of them. There is a fascinating theorem of Lovasz [L] that characterizes which vectors in $ {\mathbb Z}^E $ can be written as an integer combination of perfect matchings. However, very little is known about nonnegative integer combinations of perfect matchings. In particular, if the Berge-Fulkerson conjecture is true, then for every 3-graph $ G=(V,E) $ , there is a list of 5 perfect matchings with union $ E $ (take any 5 of the 6 perfect matchings given by the conjecture). The following weakening of this (suggested by Berge) is still open. Conjecture There exists a fixed integer $ k $ such that the edge set of every 3-graph can be written as a union of $ k $ perfect matchings. Another consequence of the Berge-Fulkerson conjecture would be that every 3-graph has 3 perfect matchings with empty intersection (take any 3 of the 6 perfect matchings given by the conjecture). The following weakening of this (also suggested by Berge) is still open. Conjecture There exists a fixed integer $ k $ such that every 3-graph has a list of $ k $ perfect matchings with empty intersection.