Open Problem Garden

This beautiful conjecture was made independently by Szekeres and Seymour in the 70's and is now widely considered to be among the most important open problems in graph theory. Note the similarity between this conjecture and the Berge-Fulkerson conjecture on perfect matchings. Attempts to prove this conjecture have lead to a variety of conjectured strengthenings, which appear on other pages. See: The circular embedding conjecture, The five cycle double cover conjecture, The faithful cover conjecture, and Decomposing Eulerian graphs.

If a graph has a nowhere-zero 4-flow then it follows from a result of Tutte that satisfies the above conjecture. Thus, by Jaeger's 4-flow theorem [J], the above conjecture is true for every 4-edge-connected graph. A cubic graph has a nowhere-zero 4-flow if and only if it is 3-edge-colorable, so the above conjecture is also true for 3-edge-colorable cubic graphs. In general, it follows from vertex splitting arguments that problem may be reduced to cubic graphs which are not 3-edge-colorable.

For a general graph with no cut-edge, Bermond, Jackson and Jaeger [BJJ] used Jaeger's 8-flow theorem [J] to prove that has a list of circuits so that every edge is contained in exactly four. Fan [F] used Seymour's 6-flow theorem [S81] to prove that G has a list of circuits so that every edge is contained in exactly six.

Let be a directed graph and let be a circuit (not necessarily a directed circuit) of . If we choose a direction to travel around , then every edge of is either traversed forward or backward. The following strengthening of the cycle double cover conjecture takes directions into account.

Conjecture  (The oriented cycle double cover conjecture)   If is an orientation of a bridgeless graph, then there is a list of circuits of with directions so that every edge of is traversed forward by exactly one circuit in and backward by exactly one circuit in .

Tutte also showed that every graph with a nowhere-zero 4-flow satisfies this conjecture. Thus, as above this conjecture is true for 4-edge-connected graphs and for 3-edge-colorable cubic graphs.

It was mentioned above that for a general graph with no bridge, there is a list of circuits containing every edge exactly four times. By taking two copies of each circuit in this list and giving them opposite directions, we have a list of circuits so that every edge is traversed forward and backward exactly four times. Luis Goddyn and I (M. DeVos) have observed that the same ideas used in Fan's article [Fa] can be used to construct a list of circuits with directions so that every edge is traversed forward and backward exactly three times. The following natural question seems to be open.

Conjecture  (The oriented cycle four cover conjecture)   If is an orientation of a bridgeless graph, then there is a list of circuits of with directions so that every edge of is traversed forward by exactly two circuits in and backward by exactly two circuits in .

Since every graph with a nowhere-zero 4-flow has a list of circuits with directions traversing every edge forward and backward exactly once, the above conjecture would follow from The three 4-flows conjecture.