# How many independent even cycles in $G(n,m)$

In the random graph model $$G(n,m)$$, how many independent even cycles are there ?

More precisely, let $$C$$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$ for $$c=0,1,\ldots$$ ?

For my purposes, it would be enough to calculate $$\mathbb{E}(2^C) := \sum_{c=0}^\infty 2^c \cdot P(C=c) = \sum_{c=0}^{m/4} 2^c \cdot P(C=c)$$

This probably varies a lot depending on which kind of $$m$$ you're looking at.

Here's a partial answer. For any $$n$$-vertex, $$m$$-edge, $$2$$-connected graph $$G$$ with odd cycles, $$C=m-n$$. We also have:

Theorem 4.3, Frieze and Karonski's Random Graphs.

Let $$m = \frac12 n(\log n + \log \log n + c_n)$$. Then $$\lim_{n \to \infty} \Pr[G(n,m) \text{ is 2-connected}] = \begin{cases}0 & \text{if } c_n \to -\infty \\ e^{-e^{-c}} & \text{if }c_n \to c \\ 1 & \text{if }c_n \to \infty.\end{cases}$$

This tells us when $$G(n,m)$$ is $$2$$-connected with high probability; odd cycles appear much earlier, and therefore $$2^C = 2^{m-n}$$ with high probability; since $$C \le m-n-1$$ always, this means $$\mathbb E[2^C] \sim 2^{m-n}$$ for such $$m$$.

For smaller $$m$$, we need to think about the number of blocks (maximal $$2$$-connected subgraphs) in $$G(n,m)$$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:

• In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
• Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
• Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).

The result about $$2$$-connected graphs also applies when the $$2$$-core of $$G$$ is $$2$$-connected, since we can delete vertices of degree $$1$$ without changing $$m-n$$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.

The claim that $$C \ge m-n$$ when $$G$$ is $$2$$-connected might be well-known, but it's new to me, so I will prove it.

In this case, the cycle space is generated by $$m-(n-1)$$ cycles. To show that the even cycle space is generated by $$m-n$$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.

Take any two odd cycles. Let $$u_1, v_1$$ be three vertices on one cycle, and $$u_2, v_2$$ be three vertices on another. The graph where we add a vertex $$x_i$$ adjacent to $$u_i, v_i$$ for $$i=1,2$$ is also $$2$$-connected, so there are $$2$$ disjoint paths from $$x_1$$ to $$x_2$$. Deleting $$x_1$$ and $$x_2$$ produces, without loss of generality, a path $$P$$ from $$u_1$$ to $$u_2$$ and a path $$Q$$ from $$v_1$$ to $$v_2$$.

If we follow $$P$$ from $$u_1$$ to $$u_2$$, then go from $$u_2$$ to $$v_2$$ in the second cycle (in some direction), then follow $$Q$$ back from $$v_2$$ to $$v_1$$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $$u_2$$ to $$v_2$$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $$2$$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.