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.
