这篇论文给出了一个漂亮的下界：符合条件的立方图至少有2^(n/2-1)个电路双覆盖，和图论猜想完美匹配，图论爱好者可以看看。
Szekeres-Seymour的圈双覆盖猜想近期被OpenAI宣布证明。本文研究立方图的计数版本，证明每个2-边连通3-边可着色的n顶点立方图至少有2^(n/2-1)个电路双覆盖，与猜想的下界一致。对于围长至少16的3-边连通立方图，本文给出一个更弱的指数下界。此外，该研究通过OpenAI使用的线性方程组提供了新的组合解释，并刻画了平面性。
Exponentially Many Circuit Double Covers
The cycle double cover conjecture of Szekeres and Seymour, the proof of which was recently announced by OpenAI, states that every bridgeless graph has a collection of cycles covering every edge exactly twice. We study the counting version of this statement for cubic graphs, where we count circuit double covers --- collections of circuits (connected 2-regular subgraphs) covering every edge twice. We show that every 2-edge-connected 3-edge-colorable cubic graph on $n$ vertices has at least $2^{n/2-1}$ circuit double covers, matching our previously conjectured general lower bound. For every 3-edge-connected cubic graph with girth at least 16 we show a weaker exponential lower bound on circuit double covers. For both of these results we use the same system of linear equations used by OpenAI in their proof, however, we provide additional combinatorial interpretation. We characterize planarity of a cubic graph by solvability of this system of equations for arbitrary nowhere-zero $\mathbb Z_2^k$-flow. We give a condition on the flow that is equivalent to existence of a 5-cycle double cover.