Does the complete graph contain the maximum number of simple cycles?

Question

Let $\mathcal{G}(n,m)$ be the set of connected, simple graphs with $n$ vertices and $m$ edges. For any graph $G$ we denote its number of simple cycles with $\mu(G)$ and and for any finite family of finite graphs $\mathcal{G}$ we define $\mu(\mathcal{G}):=\text{max}_{G \in \mathcal{G}} \{ \mu(G) \}$.

---

Let $\mathcal{G}(\mathbb{N},m) := \bigcup_{n \in \mathbb{N}} \mathcal{G}(n,m)$.

I wonder if the following statement is true:

Let $m \in \mathbb{N}$ such that there is a complete graph $G_{,m}$ with $m$ edges. Then $\mu (\mathcal{G}(\mathbb{N},m))=\mu(G_{,m})$.

Remark: If $m$ is the number of edges of some complete graph $G_{,m}$, then, since we only consider connected and simple graphs, $\mathcal{G}(\mathbb{N},m)$ cannot contain any graph with less vertices than $G_{,m}$; on the other side, there is also an upper limit on the number of vertices of the graphs in $\mathcal{G}(\mathbb{N},m)$: $m+1$. Therefore the number $\mu (\mathcal{G}(\mathbb{N},m))$ is well defined.

Answer 1

No, not by far.

Suppose $m=\binom n2$ -- the claim is then that $K_n$ contains a maximum number of simple cycles among all graphs with $m$ edges.

But $K_n$ has strictly less than $n!$ simple cycles, whereas we can also arrange the same number of edges into $\lfloor m/3\rfloor$ triangles strung together in a circle:

      *   *   *   *   *
     / \ / \ / \ / \ / \
*---*---*---*---*---*---*
 \ /                   / \
  *---*---*---*---*---*---*
   \ / \ / \ / \ / \ /
    *   *   *   *   *

which has at least $2^{\lfloor m/3\rfloor}$ different simple cycles.

And $$ \log_2(n!) < \log_2(n^n) = n\log_2 n $$ which grows strictly slower than $\lfloor m/3\rfloor=\bigl\lfloor\frac{n^2-n}{6}\bigr\rfloor \in \Omega(n^2)$.

So for large enough $n$ (by the crude $n!$ estimate, $n\ge 19$ will do), the complete graph $K_n$ always has fewer simple cycles than the necklace-of-triangles graph with the same number of edges.