Talk:Cycle double cover

Equivalence of C.D.C.C. and Strong Embedding Conjecture

There appears to be an error in the Circular Embedding Conjecture section. The method of expanding vertices to form a cubic graph, finding a strong embedding of this cubic graph, and then contracting the edges to undo the vertex expansions, does not always give a strong embedding of the original graph. Specifically, it fails when the end-vertices of an expanded edge appear in a facial cycle, but the edge itself does not (i.e., the expanded edge is a chord of the facial cycle). When that edge is contracted we are left with a facial walk that is not a cycle.

An example of this issue for a certain vertex expansion and strong embedding of K₅ is illustrated in the linked image. Of course, there are many possible vertex expansions of K₅ and then multiple c.d.c.s of each of those expansions (e.g. the expanded graph in the attached example, the Petersen graph, has ten distinct c.d.c.s). Thus in this example we can choose a different expansion of K₅ or a different c.d.c. of the Petersen graph and the method will work. But in general, it is not clear that for every 2-connnected graph we can always find an appropriate vertex expansion and corresponding c.d.c.

The section in this Wikipedia page that describes this method cites Jaeger's survey article from 1985, yet the method does not appear there, and Jaeger does not claim the two conjectures are equivalent beyond the cubic case. Other sources also do not claim that the C.D.C.C. and the Strong Embedding Conjecture are equivalent. On page 153 of his 1997 monograph, Integer Flows and Cycle Covers of Graphs, Zhang notes the equivalence of the cubic cases of the two conjectures. But on the same page when discussing circular 2-cell embeddings Zhang states, "one cannot assume that every bridgeless graph has such an embedding, since that is an even stronger open problem." Mohar and Thomassen cite both Jaeger 1985 and Zhang 1997 when discussing the C.D.C.C. and Strong Embedding Conjecture in their 2001 textbook Graphs on Surfaces (coincidentally also on page 153 of their book). They describe the Strong Embedding Conjecture as "stronger" than the C.D.C.C., so they interpreted Jaeger as not claiming a full equivalence of the conjectures.

I'd guess the confusion in this Wikipedia page stemmed from the following sentence on page 3 of Jaeger's article: "...the strong embedding conjecture restricted to cubic graphs in [sic] equivalent to the double cover conjecture restricted to cubic graphs (which in turn is equivalent, as we shall see later, to the general double cover conjecture)." I think the statement in the parenthesis refers to the fact that if a counterexample to the C.D.C.C. exists, the minimal such graph must be cubic. I could see how this could be misinterpreted as suggesting a full equivalence though.

Anyway, I'd suggest at least deleting everything in the second paragraph of the Circular Embedding Conjecture section after the first two sentences. I would have gone ahead and done this myself, but this is my first time editing Wikipedia, so I wanted to take a more cautious approach - perhaps there is some protocol I am not aware of that I need to follow in this case. If no one has any issues, then I'll go ahead and delete those sentences in 24 hours (or maybe one of the past authors of this page wants to do it themselves). Sp bowen (talk) 18:06, 6 April 2024 (UTC)[reply]

Replacing Biconnected with 2-Connected

Regarding a separate issue with this article, I'd suggest replacing all instances of "biconnected" with "2-connected". The only difference between biconnectedness and 2-connectedness is the case of the complete graph on two vertices, which is considered biconnected but not 2-connected. But given that the Strong Embedding Conjecture makes a claim with respect to closed 2-cell embeddings, and the face created by a single edge with two end-vertices embedded in the plane is not homeomorphic to a closed disk, it can't be considered a strong embedding.

Also, Jaeger's 1985 survey article uses 2-connected instead of biconnected when stating the Strong Embedding Conjecture.

As in the previous topic I posted about, I'm just letting other more experienced editors know what I think should be changed instead of jumping right in and making the change immediately. Let me know if there is an issue, otherwise I'll make these changes in 24 hours. Sp bowen (talk) 18:08, 6 April 2024 (UTC)[reply]

"2-connected" is too ambiguous. It usually means 2-vertex-connected but could instead be thought of as meaning 2-edge-connected. In contrast, biconnected is unambiguous. —David Eppstein (talk) 00:37, 7 April 2024 (UTC)[reply]

I agree that "2-connected" is ambiguous. But if we state the Strong Embedding Conjecture as "every biconnected graph has a circular embedding onto a manifold," then the conjecture is trivially false due to the K₂ case.

Unless we use a different definition than the one on the biconnected wikipedia page, the clearest option might be to use "2-vertex-connected". k-vertex-connectedness requires there to be more than k vertices in a graph, letting us avoid the 2 vertex case. Sp bowen (talk) 03:56, 7 April 2024 (UTC)[reply]

Ok, I can see your point. Treating K2 as biconnected is necessary for biconnected components but the wrong choice here. 2-vertex-connected may be best. —David Eppstein (talk) 15:19, 7 April 2024 (UTC)[reply]