Counting Cycle Double Covers

Radek Hušek, 27 Feb 2023

We study a counting version of Cycle Double Conjecture. We give an almost-exponential lower-bound for graphs with a surface embedding of representativity at least \(4\). We also prove an exponential lower-bound for planar graphs. We conjecture that any bridgeless cubic graph has at least \(2^{n/2-1}\) circuit double covers and we show an infinite class of graphs for which this bound is tight.