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.

  • $\begingroup$ If there are cycles, there are infinitely many; you need to characterise them further. $\endgroup$ – joriki Jun 24 '16 at 12:47
  • $\begingroup$ By a cycle I mean a cycle that does not cross itself; if we denote this cycle with $(v_1,...,v_k)$ then I do not allow repetitions in the set of $v_i$. Is that what you refer? $\endgroup$ – A2012N Jun 24 '16 at 12:51
  • $\begingroup$ @joriki that is wrong. Because there is a fixed number of edges, eventually our value becomes constant regardless of the number of vertices. $\endgroup$ – Jacob Wakem Jun 24 '16 at 12:53
  • $\begingroup$ @A2012N: Yes, that's what I meant. I'd suggest to use speak of "simple cycles" in the question to make that explicit. $\endgroup$ – joriki Jun 24 '16 at 12:55
  • $\begingroup$ @JacobWakem: That's a misunderstanding. I wasn't saying that the number of cycles grows without bounds as the number of vertices increases, but that already any finite graph, if it contains any cycles at all, contains infinitely many cycles, if the cycles are not restricted to be simple cycles. $\endgroup$ – joriki Jun 24 '16 at 12:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.