Cycle double cover conjecture

# Cycle Double Cover Conjecture

## Concepts

The following concepts are used at this website. Here you can find an explanation of these concepts.
• Admissable: p: E -> Z is admissable if p(e) satisfies:
• p is nonnegative
• p(S) is even for every edge-cut S
• p(e) <= p(S)/2 for every edge-cut S and edge e in S
• Bridge: A bridge is an edge of the graph with the property that when deleted, the number of connected components of the graph increases. You can also state that an edge is a bridge if and only if it is not contained in any cycle.
• Combatible decomposition: A compatible decomposition of (G,P) (where P is a transition system) is a list of edge-disjoint cycles with union G so that every cycle contains at most one edge from every member of P(v).
• Cubic graphs: Cubic graphs are 3-regular graphs. All nodes of a n-regular graph have degree n.
• Cycle-cover: An (m,n)-cycle-cover of G is a list of m cycles so that every edge of G is contained in exactly n.
• Edge-connected graph: A k-edge-connected graph will still be connected when removing less than k (random) edges.
• Eulerian graph: An Eulerian graph is a graph with an Eulerian path or a connected graph of which every vertex has even degree.
• Face-colorable with k colors: A coloring of the faces of a planar graph with k colors such that two faces that share a boundary have different colors assigned.
• Faithful cover: Let G=(V,E) and p: E -> Z. A list of cycles of G is a faithful (cycle) cover of (G,p) if every edge e of G occurs in exactly p(e) cycles of the list.
• Nowhere-zero flow: A nowhere-zero k-flow is a flow f through a graph such that -k =< f(e) =< k and f(e) not equal to 0 for every edge e.
• Planar: A graph is called planar when it is possible to draw the graph on the plane without crossing edges.
• Transition system: Let G be an Eulerian graph and for every vertex v, let P(v) be a partition of the edges incident with v. We call P a transition system. If every member of P(v) has size at most k (for every v), then we call P a k-transition system.