# The upper bound of edges of the generalized cactus graphs

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle.

The following is well known about the upper border for cactus graph class.

Theorem 1. The maximum number of edges in a simple $$n$$-vertex cactus $$G$$ is $$\left\lfloor{\frac{3(n-1)}{2}}\right\rfloor$$.The bound is achieved by a set of $$\lfloor (n − 1)/2 \rfloor$$ triangles sharing a single vertex, plus one extra edge to a leaf if $$n$$ is even.

The theorem can be found on page 160 of West's book. The proof content can also be easily referred to the answers in its appendix.

• West D B. Introduction to graph theory[M]. Upper Saddle River: Prentice hall, 2001.

I want to think about a broader graph class than the cactus class. It is a connected graph in which every edge belongs to at most $$k$$ simple cycle. I do not know whether a definition of this graph class exists. We'll temporarily call it the $$k$$-cactus graph. So we have a similar problem with the upper bound of the edge of the $$k$$-cactus graph.

Problem 1. What is the maximum number of edges in a simple $$n$$-vertex $$k$$-cactus graph?

In particular, $$k=2$$ is what we care about most.

Appendix: The four proofs of Theorem 1.

• Hello! Do you have any results about these 2-cactus graphs in which every edge belongs to at most 2 simple cycles? Commented May 6, 2023 at 7:23
• @BjørnKjos-Hanssen Thank you very much for your interest in this question. I did prove a result privately last year. I'll have time to add this proof later. Commented May 6, 2023 at 12:44
• @BjørnKjos-Hanssen Due to the answer being too long, we have written an article, which should soon be uploaded to arXiv (if not, and you're interested, I will send it to your email address, hoping I can find your correct email). There are more questions worth further exploration in it, and perhaps there is a possibility for collaboration. Commented Jun 28, 2023 at 13:36
• Sounds good! $\phantom{...}$ Commented Jun 29, 2023 at 3:45
• @BjørnKjos-Hanssen See arxiv.org/abs/2307.08039. We have just posted it on arXiv. Commented Jul 18, 2023 at 3:12

For $$k=2,3,4$$, we solved this question. But for large $$k$$, we may need more deep tools.