Reducible Configurations
One possible attack on the cycle double cover problem would be to show that there cannot exist a minimum counterexample, by proving that any graph contains a reducible configuration, a subgraph that can be replaced by a smaller subgraph in a way that would preserve the existence or nonexistence of a cycle double cover. For instance, if a cubic graph contains a triangle, a Δ-Y transform will replace the triangle by a single vertex; any cycle double cover of the smaller graph can be extended back to a cycle double cover of the original cubic graph. Therefore, a minimal counterexample to the cycle double cover conjecture must be a triangle-free graph, ruling out some snarks such as Tietze's graph which contain triangles. Through computer searches, it is known that every cycle of length 11 or less in a cubic graph forms a reducible configuration, and therefore that any minimal counterexample to the cycle double cover conjecture must have girth at least 12.
Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations. Every reducible configuration contains a cycle, so for every finite set S of reducible configurations there is a number γ such that all configurations in the set contain a cycle of length at most γ. However, there exist snarks with arbitrarily high girth, that is, with arbitrarily high bounds on the length of their shortest cycle. A snark G with girth greater than γ cannot contain any of the configurations in the set S, so the reductions in S are not strong enough to rule out the possibility that G might be a minimal counterexample.
Read more about this topic: Cycle Double Cover
Famous quotes containing the word reducible:
“The terrible tabulation of the French statists brings every piece of whim and humor to be reducible also to exact numerical ratios. If one man in twenty thousand, or in thirty thousand, eats shoes, or marries his grandmother, then, in every twenty thousand, or thirty thousand, is found one man who eats shoes, or marries his grandmother.”
—Ralph Waldo Emerson (1803–1882)