#  On the sizes of generalized cactus graphs ††thanks: The work is supported
by the National Natural Science Foundation of China (Grant No. 12271157) and
the Natural Science Foundation of Hunan Province, China (Grant No.
2022JJ30028).

Licheng Zhang, Yuanqiu Huang
College of Mathematics and Statistics
Hunan Normal University, Changsha 410081, P.R. China
Email<EMAIL_ADDRESS>author. Email<EMAIL_ADDRESS>
###### Abstract

A cactus is a connected graph in which each edge is contained in at most one
cycle. We generalize the concept of cactus graphs, i.e., a $k$-cactus is a
connected graph in which each edge is contained in at most $k$ cycles where
$k\geq 1$. It is well known that every cactus with $n$ vertices has at most
$\lfloor\frac{3}{2}(n-1)\rfloor$ edges. Inspired by it, we attempt to
establish analogous upper bounds for general $k$-cactus graphs. In this paper,
we first characterize $k$-cactus graphs for $2\leq k\leq 4$ based on the block
decompositions. Subsequently, we give tight upper bounds on their sizes.
Moreover, the corresponding extremal graphs are also characterized. However,
the case of $k\geq 5$ remains open. For the case of 2-connectedness, the range
of $k$ is expanded to all positive integers in our research. We prove that
every $2$-connected $k~{}(\geq 1)$-cactus graphs with $n$ vertices has at most
$n+k-1$ edges, and the bound is tight if $n\geq k+2$. But, for $n<k+1$,
determining best bounds remains a mystery except for some small values of $k$.

Keywords: $k$-cactus, size, extremal graph

MSC: 05C35, 05C38

##  1 Introduction

Only finite simple graphs are considered. The order of a graph is its number
of vertices and the size is its number of edges. A tree  is a connected graph
that contains no cycles, and a cactus (also known as Husimi tree [4]) is a
connected graph in which each edge is contained in at most one cycle.
Obviously, the cactus family includes trees. Cactus graphs are a well-studied
graph class, both in terms of their structure and algorithms. For example, the
family of cactus graphs is closed under graph minor operations, and they can
be characterized by a single forbidden minor, the diamond graph obtained by
removing an edge from the complete graph $K_{4}$ [2]. Some combinatorial
optimization problems, like facility location problems and finding the fast
search number, which are NP-hard for general graphs, can be solved in
polynomial time for cactus graphs [1, 10]. It is worth noting that although
the structure of cactus graphs is relatively simple, some problems remain
unsolved. One notable example is the well-known Rosa’s conjecture [6].

From the perspective of enumerating the number of cycles containing edges,
cactus graphs can be extended further. We say that a connected graph is a
$k$-cactus if each edge is contained in at most $k$ cycles where $k\geq 1$. In
particular, 1-cactus graphs are cactus graphs. While the concept “$k$-cactus”
may seem novel, there are early results on analogous cycle-edge patterns. For
example, in 1973, Toida [7] proved that a graph $G$ is an Eulerian graph if
and only if every edge of $G$ lies on an odd number of cycles. In 1988, Erdős
[3] established that $|E(G)|\geq\frac{3}{2}\left(|V(G)|-1\right)$ if each edge
of graph $G$ lies in at least one triangle (i.e., $C_{3}$).

Clearly, every tree with $n$ vertices has exactly $n-1$ edges. The following
well-known theorem gives an upper bound on the sizes of cactus graphs. The
theorem is explicitly documented in some books, such as the textbook [8], or
implied in [5] (refer to the first exercise in page 73), yet its original
authorship remains a mystery so far.

######  Theorem 1 (p.160, [8]).

Let $G$ be a cactus with $n$ vertices. Then
$|E(G)|\leq\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.

Motivated by Theorem 1, we pose the following natural problem on $k$-cactus
graphs where $k\geq 2$.

######  Problem 1.

Let $G$ be a $k$-cactus with $n$ vertices where $k\geq 2$. Can we establish a
(tight) upper bound $f(n,k)$ on sizes of $G$?

For the case $k=2,3,4$, we answer the above problem. Moreover, the
corresponding extremal graphs are also characterized. But for $k\geq 5$
(especially for larger or more general values of $k$), the problem remains
open.

The paper is structured as follows. In Section 2, we introduce some
terminology, definitions, and a few preliminary lemmas. In Section 3, we
characterize $k$-cactus graphs for $2\leq k\leq 4$ in terms of the block
decompositions. In Section 4, we first prove that every $2$-connected
$k~{}(\geq 1)$-cactus graphs with $n$ vertices has at most $n+k-1$ edges, and
the bound is tight if $n\geq k+2$. Next we give tight upper bounds on sizes of
$k$-cactus graphs where $2\leq k\leq 4$, and the corresponding extremal graphs
are also characterized. We conclude in Section 5 with a discussion of some
open questions.

##  2 Preliminaries

Let $G$ be a graph. Let $v$ be a vertex of $G$. We denote by $N_{G}(v)$ the
set of vertices adjacent to $v$, and by $I_{G}(v)$ the set of edges incident
with $v$. A component of $G$ is a connected subgraph $H$ such that no subgraph
of $G$ that properly contains $H$ is connected. A cut-vertex is a vertex whose
removal increases the number of components. We write $G-v$ or $G-S$ for the
subgraph obtained by deleting a vertex $v$ or set of vertices $S$. An induced
subgraph is a subgraph obtained by deleting a set of vertices. We write $G[T]$
for $G-\bar{T}$, where $\bar{T}=V(G)\setminus T$. A block of $G$ is a maximal
connected subgraph of $G$ that has no cut-vertex. A block is called a
$H$-block if the block is isomorphic to the graph $H$.

For a non-negative integer $n$, we denote $K_{n}$ a complete graph with $n$
vertices, and if $n\geq 3$ we denote by $C_{n}$ a cycle with $n$ vertices. The
union of graphs $G$ and $H$ is the graph $G\cup H$ with vertex set $V(G)\cup
V(H)$ and edge set $E(G)\cup E(H)$.

The subsequent observation follows directly from the definition of blocks.

######  Observation 1.

Let $G$ be a connected graph with at least $2$ vertices. If a block $H$ of $G$
is not a single edge, then $H$ is $2$-connected.

A decomposition of a graph is a list of subgraphs such that each edge appears
in exactly one subgraph in the list.

######  Lemma 1 ( [8]).

Let $G$ be a graph. Then the blocks of $G$ form a decomposition of $G$.

Let $G_{1}$ and $G_{2}$ be two vertex-disjoint graphs, and let $v_{1}\in
V(G_{1}),v_{2}\in V(G_{2})$. The coalescence of $G_{1}$, $G_{2}$ with respect
to $v_{1},v_{2}$, denoted by $G_{1}(v_{1})\diamond G_{2}(v_{2})$, is obtained
from $G_{1}$, $G_{2}$ by identifying $v_{1}$ with $v_{2}$ and forming a new
vertex $u$. In other words, $V(G_{1}(v_{1})\diamond G_{(}v_{2}))=V(G_{1})\cup
V(G_{2})\cup\\{u\\}\setminus\\{v_{1},v_{2}\\}$, and $E(G_{1}(v_{1})\diamond
G_{2}(v_{2}))=\big{(}E(G_{1})\setminus
I_{G_{1}}(v_{1})\big{)}\bigcup\big{(}E(G_{2})\setminus
I_{G_{2}}(v_{2})\big{)}\bigcup\\{ux|x\in N_{G_{1}}(v_{1})\cup
N_{G_{2}}(v_{2}))\\}$. If the identifying vertices are not specified, the
coalescence of $G_{1}$ and $G_{2}$ can be denoted as $G_{1}\diamond G_{2}$.
For a series of pairwise disjoint graphs $G_{1},G_{2},\dots,G_{t}$ where
$t\geq 3$, we define their coalescence as $G_{1}\diamond G_{2}\cdots\diamond
G_{t}$ where $G_{1}\diamond G_{2}\cdots\diamond G_{i-1}\diamond
G_{i}=(G_{1}\diamond G_{2}\cdots\diamond G_{i-1})\diamond G_{i}$ for every
$2\leq i\leq t$.

Let $G_{1},G_{2},\dots,G_{t}$ be pairwise disjoint graphs. Let $\xi$ be a
graph class that consists of each graph that is a coalescence of
$G_{1},G_{2},\dots,G_{t}$.

######  Lemma 2.

Let $G$ be a graph in $\xi$. Then $|V(G)|=\sum_{i=1}^{k}|V(G_{i})|-(t-1)$ and
$|E(G)|=\sum_{i=1}^{k}|E(G_{i})|$.

##  3 Characterization of $k$-cactus graphs for $2\leq k\leq 4$

Clearly, Lemma 1 implies that any graph has a block decomposition. Therefore,
if we clarify structures of each block of a graph, the characteristics of the
entire graph will also become clearer. It is well known that there are several
equivalent definitions of cactus graphs, one of which is that a graph is a
cactus if and only if each of its blocks is either a cycle or an edge.
Similarly, we provide a characterization of $k$-cactus graphs for $2\leq k\leq
4$ based on the block decompositions.

By Observation 1, any block with at least 3 vertices is 2-connected.
Therefore, some specialized tools for 2-connected graphs are needed. Let $F$
be a subgraph of $G$. An ear of $F$ in $G$ is a nontrival path in $G$ whose
vertex-ends lie in $F$ but whose internal vertices do not. First, we introduce
the concept of the ear decompositions. An ear decomposition of $G$ is a
decomposition $Q_{0},Q_{1},\cdots,Q_{k}$ such that $Q_{0}$ is a cycle and
$Q_{i}$ for $i\geq 1$ is an ear of $Q_{0}\cup Q_{1}\cdots\cup Q_{i-1}$. We
denote the ear decomposition in the mentioned order as
$[Q_{0},Q_{1},...,Q_{l}]$.

######  Lemma 3 (p.162, [8]).

Let $G$ be a $2$-connected graph. Then $G\cup Q$ is $2$-connected where $Q$ is
an ear of $G$ in $G\cup Q$.

The following lemma, known as the “ear decomposition theorem”, gives a
technique to construct a 2-connected graph from a cycle and paths. It will be
a key tool for characterizing 2-connected $k$-cactus graphs for $2\leq k\leq
4$.

######  Lemma 4 (Whitney, [9]).

A graph is $2$-connected if and only if it has an ear decomposition.

######  Lemma 5 (p.162, [8]).

Any two edges are contained in a cycle in a $2$-connected graph.

######  Lemma 6.

Let $G$ be a $2$-connected graph and let $uv$ be an edge. Let $Q$ be an ear of
$G$ in $G\cup Q$. If $uv$ is contained in $k$ cycles in $G$, then $uv$ is
contained in at least $k+1$ cycles in $G\cup Q$.

###### Proof.

First, the $k$ different cycles in $G$ that contain $uv$ are also preserved in
$G\cup Q$ (i.e., they are also $k$ distinct cycles that contain $uv$ in $G\cup
Q$). Additionally, by Lemma 3, $G\cup Q$ is still 2-connected, and thus $uv$
and an edge in $Q$ will lie in a common cycle $C^{\prime}$ in $G\cup Q$ by
Lemma 5. It is clear that $C^{\prime}$ is distinct from any of the $k$ cycles
containing $uv$, as desired. ∎

A $k$-theta graph denoted by $\theta(l_{1},l_{2},\dots,l_{k})$ where $k\geq 3$
is the graph obtained from $k$ internally disjoint paths of lengths
respectively $l_{1},l_{2},\dots,l_{k}$, with the same pair of end-vertices.
Notably, among these $k$ internally disjoint paths, there exists at most one
path with length one, since we only consider simple graphs. Obviously, 3-theta
graphs are our familiar theta graphs. For short, we refer to a $k$-theta graph
as a $\theta_{k}$-graph. We denote $\theta^{\prime}(p,q,r)$ as a graph
obtained by adding an ear to a theta graph $\theta(p,q,r)$ where both end-
vertices of the ear are not the vertices with degree 3 of $\theta(p,q,r)$. For
short, we denote the graph $\theta^{\prime}(p,q,r)$ by
$\theta_{3}^{\prime}$-graph.

We call a $k$-cactus $H$ is nice if there exists an edge in $H$ contained in
exactly $k$ cycles.

######  Observation 2.

Let $k$ and $l$ be integers where $0\leq k<l$. Then any $k$-cactus is an
$l$-cactus.

######  Lemma 7.

(i) Every cycle is a nice cactus. (ii) Every $\theta_{k}$-graph is a nice
$k-1$-cactus.(iii) Every $\theta_{3}^{\prime}$-graph is a nice $4$-cactus.

###### Proof.

It can verify (i) and (ii) directly, so we only prove (iii). By definition of
$\theta_{3}^{\prime}$-graph, it is obtained by adding an ear
$Q=q_{0}q_{1}\dots q_{s}$ from a theta graph $\theta(l_{1},l_{2},l_{3})$. Let
$u$ and $v$ be the unique two vertices with degree $3$ in
$\theta(l_{1},l_{2},l_{3})$. Let $P^{1}=uu_{1}^{\prime}u_{2}^{\prime}\dots
u_{l-1}^{\prime}v$, $P^{2}=uu_{1}^{\prime\prime}u_{2}^{\prime\prime}\dots
u_{l-1}^{\prime\prime}v$, and
$P^{3}=uu_{1}^{\prime\prime\prime}u_{2}^{\prime\prime\prime}\dots
u_{l-1}^{\prime\prime\prime}v$ be three internally vertex disjoint paths
connecting $u$ and $v$ where $|E(P^{i})|=l_{i}$ for $1\leq i\leq 3$.

We will discuss three cases regarding the placement of the two end-vertices of
$Q$ at the position of $\theta(l_{1},l_{2},l_{3})$.

Case 1. $\\{q_{0},q_{s}\\}\subseteq V(P^{i})$ and
$\\{q_{0},q_{s}\\}\cap\\{u,v\\}=\emptyset$ where $1\leq i\leq 3$. Without loss
of generality, we assume $i=3$, $q_{0}=u_{c}^{\prime\prime\prime}$ and
$q_{s}=u_{c+m}^{\prime\prime\prime}$ where $c$ and $m$ are integers and $c\geq
1$ and $m\geq 1$; see Fig. 1 (1) for an illustration. Let
$P^{a}=u_{c}^{\prime\prime\prime}(=q_{0})u_{c+1}^{\prime\prime\prime}\dots
u_{c+m-1}^{\prime\prime\prime}u_{c+m}^{\prime\prime\prime}(=q_{s})$. Let
$P^{b}$ be the path obtained by replacing the subpath $P^{a}$ with $Q$ in
$P^{3}$. Now, it is easy to verify that any edge on $P^{i}$ for $i=1,2$ will
be contained in exactly three cycles: $P^{i}\cup P^{3-i}$, $P^{i}\cup P^{3}$,
$P^{i}\cup P^{b}$. Clearly, $Q$ and $P^{a}$ are symmetric. Hence we only
consider $Q$, and observe that any edge in $Q$ is contained in exactly three
cycles $Q\cup P^{a}$, $P^{1}\cup P^{3}$, and $P^{2}\cup P^{b}$. We observe
that any edge of two paths $uu_{1}^{\prime\prime\prime}\dots
u^{\prime\prime\prime}_{c-1}q_{0}$ or
$q_{s}u_{c+m+1}^{\prime\prime\prime}\dots u^{\prime\prime\prime}_{l_{3}-1}v$
will be contained in exactly four cycles $P^{1}\cup P^{3}$, $P^{2}\cup P^{3}$,
$P^{1}\cup P^{4}$ and $P^{2}\cup P^{4}$.

Case 2. $\\{q_{0},q_{s}\\}\subseteq V(P^{i})$ and
$|\\{q_{0},q_{s}\\}\cap\\{u,v\\}|=1$ where $1\leq i\leq 3$. This case is
similar to Case 1, and we omit its proof. See also Fig. 1 (2) for an
illustration.

Case 3. $q_{0}\in V(P^{i})\setminus\\{u,v\\}$ and $q_{s}\in
V(P^{j})\setminus\\{u,v\\}$ where $1\leq i,j\leq 3$ and $i\neq j$. In this
case, without loss of generality, we assume $i=2$ and $j=3$; as shown in
Figure 1 (3). The vertices $q_{0}$ and $q_{s}$ divide $P^{2}$ and $P^{3}$ into
two subpaths, respectively. Let
$P^{2}_{a}=uu_{1}^{\prime\prime}u_{2}^{\prime\prime}\dots q_{0}$,
$P^{2}_{b}=q_{0}\dots u^{\prime\prime\prime}_{l_{2}-1}v$,
$P^{3}_{a}=uu_{1}^{\prime\prime\prime}u_{2}^{\prime\prime\prime}\dots q_{s}$,
$P^{3}_{b}=q_{s}\dots u^{\prime\prime\prime}_{l-1}v$. Considering symmetry, we
only need to determine the number of cycles containing any edge on $P^{1}$,
$Q$, $P^{2}_{a}$, respectively. For each edge in $P^{1}$, it is contained in
exactly four cycles $P^{1}\cup P^{2}$, $P^{1}\cup P^{3}$, $P^{1}\cup
P^{2}_{a}\cup Q\cup P^{3}_{b}$ and $P_{1}\cup P^{2}_{b}\cup Q\cup P^{3}_{a}$.
For each edge in $Q$, it is contained in exactly four cycles $Q\cup
P^{2}_{a}\cup P^{3}_{a}$, $Q\cup P^{2}_{b}\cup P^{3}_{b}$, $Q\cup
P_{b}^{3}\cup P^{1}\cup P^{2}_{a}$ and $Q\cup P^{2}_{b}\cup P^{1}\cup
P^{3}_{a}$. As for each edge in $P^{2}_{a}$, it is contained in exactly four
cycles $P^{1}\cup P^{2}$, $P^{2}\cup P^{3}$, $P^{2}_{a}\cup Q\cup P^{3}_{a}$
and $P^{2}_{a}\cup Q\cup P^{3}_{b}\cup P^{1}$.

By above discussion, every $\theta_{3}^{\prime}$-graph is a nice $4$-cactus. ∎

Figure 1:  Three ways of adding the ear $Q$ to $\theta(l_{1},l_{2},l_{3})$.

######  Lemma 8.

Let $G$ be a $2$-connected $k$-cactus where $k\geq 1$. Let
$[Q_{0},Q_{1},\cdots,Q_{l}]$ be an ear decomposition of $G$ where $Q_{0}$ is a
cycle. Then $l\leq k-1$.

###### Proof.

Let $e$ be an edge of the cycle $Q_{0}$. Then $e$ is contained in one cycle.
By repeatedly applying Lemma 6, $e$ will be contained in at least $l+1$ cycles
in $Q_{0}\cup Q_{1}\cdots\cup Q_{l}$. Since $G$ is a $k$-cactus, we have
$k\leq l+1$, yielding $l\leq k-1$. ∎

######  Theorem 2.

Let $G$ be a graph. Then the following statements hold.

  * (i)

$G$ is a $2$-cactus if and only if each block of $G$ is either an edge, a
cycle, or a $\theta_{3}$-graph.

  * (ii)

$G$ is a $3$-cactus if and only if each block of $G$ is either an edge, a
cycle, or a $\theta_{t}$-graph where $3\leq t\leq 4$.

  * (iii)

$G$ is a $4$-cactus if and only if each block of $G$ is either an edge, a
cycle, a $\theta_{3}^{\prime}$-graph, a $\theta_{t}$-graph where $3\leq t\leq
5$.

###### Proof.

Clearly, “if”-parts of the three statements (i), (ii) and (iii) follow from
Lemma 7 and Observation 2. Now we prove their “only if”-parts, respectively.
Let $B$ be a block of $G$.

For (i), it is evident that $B$ can be an edge. If $B$ is not an edge, then
$B$ is 2-connected. Then by Lemmas 4 and 8, $B$ has an ear decomposition and
at most one ear in the decomposition. So $B$ is either a cycle or a theta
graph, as desired.

For (ii), clearly, $B$ can be an edge. If not, by Lemma 4, we can assume that
$[Q_{0},\cdots,Q_{l}]$ is an ear decomposition of $B$. Furthermore, by we have
$l\leq 2$ by Lemma 8. For $l=0$, then $B$ is a cycle. As for $l=1$, $B$ is a
theta graph. For $l=2$, then by Lemma 7 (ii)-(iii), $B$ must be a
$\theta_{4}$-graph.

For (iii), clearly, $B$ can be an edge. If not, we can similarly assume that
$[Q_{0},\cdots,Q_{l}]$ is an ear decomposition of $B$. By Lemma 8, we have
$l\leq 3$. For $l\leq 2$, then $B$ can be either a cycle, a theta graph, or a
$\theta^{\prime}$-graph (by Lemma 7 (iii)). As for $l=3$, its subgraph
$Q_{0}\cup Q_{1}\cup Q_{2}$ is a $\theta_{4}$-graph or a
$\theta_{3}^{\prime}$-graph. Furthermore, if $Q_{0}\cup Q_{1}\cup Q_{2}$ is a
$\theta_{3}^{\prime}$-graph, then by Lemma 7 (iii), it is known to be a nice
4-cactus, which means there exists an edge that lies on 4 cycles. Then, by
Lemma 6 there exists at least one edge in $Q_{0}\cup Q_{1}\cup Q_{2}\cup
Q_{3}$ (i.e. $B$) being contained $5$-cycles , which contradicts the
assumption. So $Q_{0}\cup Q_{1}\cup Q_{2}$ is a $\theta_{4}$-graph. Let
$P^{1}$, $P^{2}$, $P^{3}$, $P^{4}$ be four internally disjoint paths in
$Q_{0}\cup Q_{1}\cup Q_{2}$ that connect two (unique) vertices of degree $4$.
We claim that both two end-vertices of $Q_{3}$ must be the distinct vertices
of degree 4. Otherwise, combining the assumption of $Q_{0}\cup Q_{1}\cup
Q_{2}$ with the definition of ears, we can obtain a
$\theta_{3}^{\prime}$-graph by deleting some path $P^{i}$ from $B$ where
$1\leq i\leq 4$, Based on the previous discussion, adding back $P^{i}$, there
is an edge of $B$ that lies on five cycles based on the earlier discussion, a
contradiction. This complete the proof. ∎

##  4 Upper bounds and extremal graphs

Before proving the main theorem, we give three simple lemmas without proof.

######  Lemma 9.

Let $G$ be a $\theta_{k}$-graph. Then $|V(G)|\geq k+1$ and $|E(G)|=n+k-2$.

######  Lemma 10.

Let $G$ be a $\theta^{\prime}$-graph. Then $|V(G)|\geq 4$ and $|E(G)|=n+2$.

######  Lemma 11.

Let $x$ and $y$ be two reals. Then $\lfloor x\rfloor+\lfloor
y\rfloor\leq\lfloor x+y\rfloor$.

Now we investigate some upper bounds on the sizes for 2-connected $k$-cactus
graphs.

######  Proposition 1.

Let $G$ be a $2$-connected $k$-cactus with $n$ vertices where $k\geq 1$. Then
$|E(G)|\leq n+k-1$. Moreover, the bound is tight for $n\geq k+2$.

###### Proof.

By Lemma 4, we can assume that $[Q_{0},Q_{1},\cdots,Q_{r}]$ is an ear
decomposition of $G$. Given the definition of ears,
$n=|V(Q_{0})|+\sum_{i=1}^{r}(|V(Q_{i})|-2)$ and
$|E(G)|=|E(Q_{0})|+\sum_{i=1}^{r}|E(Q_{i})|=|V(Q_{0})|+\sum_{i=1}^{r}(|V(Q_{i})|-1)=n+r$.
From Lemma 8, it follows that $r\leq k-1$, and thus $|E(G)|\leq n+k-1$.
Moreover, by Lemma 7 (ii), every $\theta_{k+1}$-graph with $n$ is a
$k$-cactus. By Lemma 9, it has at least $k+2$ vertices and exactly $n+k-1$
edges. So the bound is tight for $n\geq k+2$. ∎

The bound in Proposition 1 may not be tight when $n\leq k-1$. In the
following, we obtain some possible better bounds for cases where $n$ takes
very small values.

######  Proposition 2.

Let $G$ be a $2$-connected $k$-cactus with $n$ vertices where $k\geq 1$. Then

  * (i)

for $n=3$ and every $k$, then $G\cong K_{3}$ and $|E(G)|=3$.

  * (ii)

for $n=4$, if $k=2,3$ then $|E(G)|\leq 5$, with equality if and only if
$G\cong\theta(1,2,2)$; if $k=4$, then $|E(G)|\leq 6$, with equality if and
only if $G\cong K_{4}$;

  * (iii)

for $n=5$, if $k=2$, then $|E(G)|\leq 6$, with equality if and only if
$G\cong\theta(1,2,2)$ or $\theta(1,2,3)$; if $k=3$, $|E(G)|\leq 7$, with
equality if and only if $G\cong\theta(1,2,2,2)$; if $k=4$, then $|E(G)|\leq 7$
with equality if and only if $G\cong\theta(1,2,2,2)$, $\tilde{\theta}_{1}$ or
$\tilde{\theta}_{2}$, where $\tilde{\theta}_{1}$ and $\tilde{\theta}_{2}$ are
shown in Fig. 2 (b)-(c), respectively.

###### Proof.

(i). It is obvious.

(ii). By Theorem 2 (ii) and (iii), $K_{4}$ is a nice $4$-cactus which means
that $K_{4}$ is not a $k$-cactus where $k<4$. Moreover, it is easy to see that
$\theta(1,2,2)$ is the unique $2$-cactus with $5$ edges. So (ii) can be
derived directly.

(iii). By Proposition 1, $E(G)\leq 6$ if $k=2$ or $E(G)\leq 7$ for $k=3$. It
is easy to verify that graphs with sizes achieving the equalities are
$\theta(1,2,2)$ for $k=2$ and $\theta(1,2,2,2)$ for $k=3$, respectively. For
$k=4$, as every $\theta_{4}$-graph has at least $6$ vertices, $G$ can be a
cycle, or a $\theta_{3}^{\prime}$-graph by Theorem 2 (iii). Combing this with
Lemmas 9 and 10, we have $|E(G)|\leq 7$. One can check that a 2-connected
4-cactus with 5 vertices and 7 edges is either $\theta(1,2,2,2)$,
$\tilde{\theta}_{1}$, or $\tilde{\theta}_{2}$. ∎

Figure 2: All 2-connected $4$-cactus graphs with $5$ vertices and $7$ edges.

Now we prove the main theorems.

######  Theorem 3.

Let $G$ be a $k$-cactus with $n$ vertices where $2\leq k\leq 3$. Then
$|E(G)|\leq\left\lfloor\frac{(2k+1)(n-1)}{k+1}\right\rfloor$. Moreover, the
bound is tight.

###### Proof.

We apply induction on the number of blocks of $G$. Let $l$ be the number of
blocks of $G$. Clearly, if $l=1$, then $|E(G)|=n-1$ if $n\leq 2$. If $n=3$,
then $|E(G)|=3$ by Proposition 2 (i). If $n=4$, then $|E(G)|\leq 5$ by
Proposition 2 (ii). If $n\geq 5$, then $|E(G)|\leq n+k-1$ by Proposition 1. In
either case, $|E(G)|\leq\lfloor(2k+1)(n-1)/k\rfloor$ for $k=2,3$.

A graph that has more than one block is not a single block, so it has a cut-
vertex $v$. Let $S$ be the vertex set of one component of $G-v$. A graph that
has more than one block is not a single block, so it has a cut-vertex $v$. Let
$S$ be the vertex set of one component of $G-v$. Let $G_{1}=G[S\cup\\{v\\}]$,
and let $G_{2}=G-S$. Both $G_{1}$ and $G_{2}$ are $k$-cactus graphs, and every
block of $G$ is a block in exactly one of $G_{1}$ and $G_{2}$. Thus each has
fewer blocks than $G$, and we can apply the induction hypothesis to obtain
$|E\left(G_{i}\right)|\leq$
$\left\lfloor(2k+1)\left(|V\left(G_{i}\right)|-1\right)/(k+1)\right\rfloor$
for $i=1,2$. Since $v$ belongs to both graphs $G_{1}$ and $G_{2}$, we have
$|V(G_{1})|+|V(G_{2})|=n+1$. We thus have

$\displaystyle|E(G)|$
$\displaystyle=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|$
$\displaystyle\leq\left\lfloor\frac{(2k+1)(|V(G_{1})|-1)}{k+1}\right\rfloor+\left\lfloor\frac{(2k+1)(|V(G_{2})|-1)}{k+1}\right\rfloor$
$\displaystyle\leq\left\lfloor\frac{(2k+1)(|V(G_{1})|-1)}{k+1}+\frac{(2k+1)(|V(G_{2})|-1)}{k+1}\right\rfloor$
(4.1) $\displaystyle=\left\lfloor\frac{(2k+1)(n-1)}{k+1}\right\rfloor,$

in which the inequality (4.1) is follows from Lemma 11.

We delay explaining the tightness of the bound until Theorems 5 and 6. ∎

Here, one might wonder whether the bound in Theorem 3 still holds for $k\geq
4$. Regrettably, the answer may be negative. For example, it is no longer
correct when $k=4$; see Theorem 4.

######  Theorem 4.

Let $G$ be a $4$-cactus with $n$ vertices. Then

$|E(G)|\leq\begin{cases}2n-2&\text{if}~{}n\equiv 1\pmod{3},\\\
2n-3&\text{otherwise.}\\\ \end{cases}$

Moreover, these bounds are tight.

###### Proof.

We also use induction on the number of blocks of $G$ (which is similar to
Theorem 3 except for some minor details). Let $l$ be the number of blocks of
$G$. We first consider the case when $l=1$. If $n\leq 2$ $|E(G)|=n-1$ and
$|E(G)|=3$ if $n=3$. By Proposition 2 (ii)–(iii), $|E(G)|\leq 6$ if $n=4$ and
$|E(G)|\leq 7$ if $n=5$. As for $n\geq 6$, we have $|E(G)|\leq n+3$ by
Proposition 1. In either case, $|E(G)|\leq 2n-2$ when $n\equiv 1\pmod{3}$ and
$|E(G)|\leq 2n-3$ when $n\equiv 0~{}\text{or}~{}2\pmod{3}$.

A graph that has more than one block is not a single block, so it has a cut-
vertex $v$. Let $S$ be the vertex set of one component of $G-v$. A graph that
has more than one block is not a single block, so it has a cut-vertex $v$. Let
$S$ be the vertex set of one component of $G-v$. Let $G_{1}=G[S\cup\\{v\\}]$,
and let $G_{2}=G-S$. Both $G_{1}$ and $G_{2}$ are 4-cactus graphs, and every
block of $G$ is a block in exactly one of $G_{1}$ and $G_{2}$, and thus each
has fewer blocks than $G$. Hence by the induction hypothesis, we have
$|E(G_{i})|\leq 2|V(G_{i})|-2$ when $|V(G_{i})|\equiv 1\pmod{3}$ and
$|E(G_{i})|\leq 2|V(G_{i})|-3$ when $|V(G_{i})|\equiv
0~{}\text{or}~{}2\pmod{3}$ for $i=1,2$.

Since $v$ belongs to both graphs $G_{1}$ and $G_{2}$, we have
$|V(G_{1})|+|V(G_{2})|=n+1$. We discuss three cases.

Case 1. $n\equiv 0\pmod{3}$. In this case, $|V(G_{i})|\equiv 1\pmod{3}$ and
$|V(G_{2-i})|\equiv 2\pmod{3}$ where $i=1$ or $i=2$, or $|V(G_{i})|\equiv
2\pmod{3}$ for $i=1,2$. In the first case, without loss of generality, we may
assume that $|V(G_{1})|\equiv 1~{}\pmod{3}$ and $|V(G_{2})|\equiv 2\pmod{3}$.
We thus have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-2)+(2|V(G_{2})|-3)=2n-3.$
For the second case, we have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-3)+(2|(G_{2})|-3)=2n-4<2n-3,$
as desired.

Case 2. $n\equiv 1\pmod{3}$. Then $|V(G_{i})|\equiv 0\pmod{3}$ and
$|V(G_{2-i})|\equiv 2\pmod{3}$ where $i=1$ or $i=2$, or $|V(G_{i})|\equiv
1\pmod{3}$ for $i=1,2$. In the first case, we may assume that
$|V(G_{1})|\equiv 0\pmod{3}$ and $|V(G_{2})|\equiv 2\pmod{3}$. We thus have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-3)+(2|V(G_{2})|-3)=2n-4<2n-2$.
For the second case, we have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-2)+(2|V(G_{2})|-2)=2n-2,$
as desired.

Case 3. $n\equiv 2\pmod{3}$. Then $|V(G_{i})|\equiv 1\pmod{3}$ and
$|V(G_{2-i})|\equiv 2\pmod{3}$ where $i=1$ or $i=2$, or $|V(G_{i})|\equiv
0\pmod{3}$ for $i=1,2$. In the first case, we may assume that
$|V(G_{1})|\equiv 1~{}\pmod{3}$ and $|V(G_{2})|\equiv 0\pmod{3}$ . We thus
have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-2)+(2|V(G_{2})|-3)=2n-3.$
For the second case, we have
$|E(G)|=|E\left(G_{1}\right)|+|E\left(G_{2}\right)|\leq(2|V(G_{1})|-3)+(2|V(G_{2})|-3)=2n-4<2n-3$.

Thus we finish our proof. ∎

A $k$-cactus graph on $n$ vertices with the largest possible number of edges
is called extremal for $n$ and $k$. Specifically, any extremal $2$-cactus with
$n$ vertices has $\left\lfloor\frac{5(n-1)}{3}\right\rfloor$ edges. Note that
the number of edges of extremal $2$-cactus graphs is the upper bound in
Theorem 3 when $k=2$.

######  Theorem 5.

Let $G$ be an extremal $2$-cactus with $n\geq 1$ vertices. The following
statements hold true.

  * (1)

If $n\equiv 0\pmod{3}$, then $G$ is obtained by coalescing $\frac{n-3}{3}$
copies of $\theta(1,2,2)$ and one copy of $K_{3}$.

  * (2)

If $n\equiv 1\pmod{3}$ and $n\neq 1$, then $G$ is obtained by coalescing
$\frac{n-1}{3}$ copies of $\theta(1,2,2)$ when $n\geq 2$; if $n=1$, then
$G\cong K_{1}$.

  * (3)

If $n\equiv 2\pmod{3}$, then $G$ is either obtained by coalescing by
$\frac{n-2}{3}$ copies of $\theta(1,2,2)$ and a copy of $K_{2}$, or obtained
by coalescing $\frac{n-5}{3}$ copies of $\theta(1,2,2)$ and either one copy of
$\theta(1,2,3)$ or two copies of $K_{3}$.

###### Proof.

First, we can easily check that the number of edges of these graphs are
$\left\lfloor\frac{5(n-1)}{3}\right\rfloor$, which also shows that the bound
given by Theorem 3 for $k=2$ is tight.

Let $G$ be an extremal 2-cactus with $n$ vertices. Let $B_{1},\ldots,B_{t}$ be
the blocks of $G$, where $t$ is the number of blocks of $G$. For the sake of
simplicity and smoothness in the subsequent proof, in what follow, we can
assume (without loss of generality) that all the blocks of $G$ share a common
vertex $u$, otherwise, we can obtain a new graph with that assumption by re-
coalescing the blocks of $G$, and Lemma 2 implies that the new graph is also
an extremal graph with same order. But we need note that although we made the
assumption on $G$, the following claims or properties on $G$ hold for any
extremal 2-cactus.

######  Claim 1.

If $B$ is a block of $G$, then $B$ has the maximum possible number of edges.

###### Proof.

Clearly, if $B$ does not have the maximum number of edges, we can replace $B$
with another block that has the same number of vertices but more edges (while
still being a 2-cactus graph). In this case, the number of edges of $G$ would
increase, contradicting the premise. ∎

######  Claim 2.

Each block of $G$ has at most $5$ vertices.

###### Proof.

Suppose that there exists a block, namely $B_{1}$, with at least 6 vertices.
If $t=1$, i.e., $G\cong B_{1}$, then by Proposition 1, $E(G)\leq
n+1<\left\lfloor\frac{5(n-1)}{3}\right\rfloor$, a contradiction. If $G$ has
more than two blocks. Recall that $u$ is the unique cut vertex of $G$. Let
$G^{\prime}=G[V(G)\setminus\\{V(B_{1}-u)\\}$]. Clearly, $B_{1}$ and
$G^{\prime}$ are connected. Thus

$\displaystyle|E(G)|$ $\displaystyle=|E(G^{\prime})+|E(B_{1})|$
$\displaystyle\leq\left\lfloor\frac{5(|V(G^{\prime})|-1)}{3}\right\rfloor+(|V(B_{1})|+1)$
$\displaystyle=\left\lfloor\frac{5(|V(G^{\prime})|-1)}{3}+|V(B_{1})|+1\right\rfloor$
$\displaystyle=\left\lfloor\frac{5(n-1)}{3}-\frac{2|V(B_{1})|-8}{3}\right\rfloor.$

Since $|V(B_{1})\geq 6$, we have $\frac{2|V(B_{1})|-8}{3}\geq\frac{4}{3}>1$.
Thus $|E(G)|\leq\left\lfloor\frac{5(n-1)}{3}\right\rfloor-1$, a contradiction.
∎

######  Claim 3.

$G$ has at most one block with exactly $5$ vertices; if the block exists, it
is a $\theta(1,2,3)$-block.

###### Proof.

Suppose that $G$ has two or more blocks with exactly $5$ vertices. Let $B_{1}$
and $B_{2}$ be such blocks. Combing Claim 1 with Proposition 2 (iii), we have
$|E(B_{1})|=|E(B_{2})|=6$. Let $B^{*}=B_{1}\cup B_{2}$ and
$G^{\prime}=G[V(G)\setminus\\{V(B^{*}-u)\\}$. Clearly,
$|V(B^{*})|=9,|E(B^{*})|=12$ and $|V(G^{\prime})|+|V(B^{*})|=n+1$. Therefore,
we have
$|E(G)|=|E(G^{\prime})+|E(B^{*})|\leq\left\lfloor\frac{5(|V(G^{\prime})|-1)}{3}\right\rfloor+12=\left\lfloor\frac{5(n-1)}{3}-\frac{4}{3}\right\rfloor\leq\left\lfloor\frac{5(n-1)}{3}\right\rfloor-1$,
a contradiction. Furthermore, by Claim 1 and Theorem 1, if there is a block
with exactly $5$ vertices, then it is a $\theta(1,2,3)$-block. ∎

######  Claim 4.

$G$ has at most two blocks with exactly $3$ vertices; if these blocks exist,
they are $K_{3}$-blocks.

###### Proof.

By Claim 1, any block with exactly $3$ vertices is isomorphic to $K_{3}$.
Suppose for a contradiction, that $G$ has three or more blocks with exactly
$3$ vertices. Let $B_{1},B_{2}$ and $B_{3}$ be such blocks. Let
$B^{*}=B_{1}\cup B_{2}\cup B_{3}$ and
$G^{\prime}=G[V(G)\setminus\\{V(B^{*}-u)\\}$. Clearly,
$|V(B^{*})|=7,|E(B^{*})|=9$ and $|V(G^{\prime})|+|V(B^{*})|=n+1$. Therefore,
we have
$|E(G)|=|E(G^{\prime})|+|E(B^{*})|\leq\left\lfloor\frac{5(|V(G^{\prime})|-1)}{3}\right\rfloor+9=\left\lfloor\frac{5(n-1)}{3}\right\rfloor-1$,
a contradiction. ∎

######  Claim 5.

$G$ has at most one $K_{2}$-block.

###### Proof.

If there are two or more $K_{2}$-blocks, then we can add an edge between two
different leaves of $G$, and the resulting new graph is still a 2-cactus
graph, but with more edges, a contradiction. ∎

Due to Claims 1-5, we deduce the following property of $G$.

######  Property 1.

Any block of $G$ is isomorphic to either $K_{2}$, $K_{3}$, $\theta(1,2,2)$, or
$\theta(1,2,3)$. Additionally, the number of blocks isomorphic to $K_{2}$ or
$\theta(1,2,3)$ is at most $1$ each, and the number of blocks isomorphic to
$K_{3}$ is at most $2$.

Now, we discuss three cases according to the remainder of $n$ divided by 3. We
rewrite the upper bound $\left\lfloor\frac{5(n-1)}{3}\right\rfloor$ as:

$|E(G)|=\begin{cases}5l-2&\text{if}~{}n=3l,\\\ 5l&\text{if}~{}n=3l+1,\\\
5l+1&\text{if}~{}n=3l+2.\end{cases}$

Case 1. $n=3l$. We need to prove that each block of $G$ is either $K_{3}$ or
$\theta(1,2,2)$, and the number of $K_{3}$-blocks is exactly one. Due to
Property 1, it suffices to show that $G$ does not contain $\theta(1,2,3)$ and
$K_{2}$ as its blocks, and $G$ contain exactly one $K_{3}$. Suppose that $G$
contains a block, namely $B_{1}$, which is isomorphic to $\theta(1,2,3)$ or
$K_{2}$. Let $G^{\prime}=G[V(G^{\prime})\setminus\\{V(B_{1}-u)\\}$]. If
$B_{1}\cong\theta(1,2,3)$, then clearly, $|V(B)|=5$ and
$|V(G^{\prime})|=n-4=3l-4=3(l-2)+2$. Then
$|E(G)|=|E(G^{\prime})|+|E(B_{1})|\leq(5(l-2)+1)+6=5l-3<5l-2$, a
contradiction. Similarly, if $B_{1}\cong K_{2}$, then clearly $|V(B)|=2$ and
$|V(G^{\prime})|=n-1=3l-1=3(l-1)+2$. Then
$|E(G)|=|E(G^{\prime})+|E(B_{1})|\leq(5(l-1)+1)+1=5l-3<5l-2$, a contradiction.

Now we prove that $G$ has exactly a $K_{3}$-block. If there does not exist
$K_{3}$-blocks, then by the previous analysis every block is a copy of
$\theta(1,2,2)$. Then $|E(G)|$ will be a multiple of 3 plus 1, which
contradicts the premise of $s=0$. By Property 1, $G$ has at most two
$K_{3}$-blocks. If there exist two blocks, namely $B_{1}$ and $B_{2}$,
isomorphic to $K_{3}$, we assume that $B=B_{1}\cup B_{2}$ and
$G^{\prime}=G[V(G^{\prime})\setminus\\{V(B-u)\\}$], then $|V(B)|=5$ and
$|V(G^{\prime})|=3(l-2)+2$. Similarly, $|E(G)|=|E(G^{\prime})|+|E(B)|\leq
5l-1$, a contradiction. Thus, we have proved the desired result.

Case 2. $n=3l+1$. Clearly, $n$=1, we have $G\cong K_{1}$. So we assume that
$n\geq 4$. Suppose that there is a block of $G$, namely $B_{1}$, which is not
isomorphic to $\theta(1,2,2)$. Let
$G^{\prime}=G[V(G)\setminus\\{V(B_{1}-u)\\}$]. For $B_{1}\cong K_{2}$, note
that $|V(G^{\prime})|=3l$. Thus
$|E(G)|=|E(G^{\prime})|+|E(B_{1})|\leq(5l-2)+1=5l-1<5l$, a contradiction. For
$B_{1}\cong K_{3}$, now $|V(G^{\prime})|=3(l-1)+2$. Thus
$|E(G)|=|E(G^{\prime})|+|E(B_{1})|\leq(5(l-1)+1)+3=5l-1<5l$, a contradiction.
For $B_{1}\cong\theta(1,2,3)$, now $|V(G^{\prime})|=(3l+1)-4=3(l-1)$. Thus,
$|E(G)|=|E(G^{\prime})|+|E(B_{1})|\leq(5(l-1)-2)+6=5l-1\leq 5l$, a
contradiction. Therefore, every block of $G$ is isomorphic to $\theta(1,2,2)$.

Case 3. $n=3l+2$. First, it is impossible that every block of $G$ is
isomorphic to $K_{3}$; otherwise, $n\equiv 1\pmod{3}$, which contradicts the
assumption. Next, we claim that if $G$ has a block, namely $B_{1}$, isomorphic
to $K_{3}$, then $G$ will contain exactly two $K_{3}$-blocks . Let $B_{1}$
then let $G^{\prime}=G[V(G)\setminus\\{V(B_{1}-u)\\}]$. Clearly, $G^{\prime}$
is also an extreme graph with $3l$ vertices. So, by the proof of Case 1,
$G^{\prime}$ has exactly one $K_{3}$-block, and hence $G$ has exactly two
$K_{3}$-blocks. Therefore, the following three cases (i)-(iii) are all
possible: (i) $G$ has exactly one $K_{2}$-block; (ii) $G$ has exactly one
$\theta(1,2,3)$-block; (iii) $G$ has two $K_{3}$-blocks. Moreover, we show
that these three cases are mutually exclusive. Assume (i) and (ii) occur
together, i.e., $G$ contains one $K_{2}$-block, namely $B_{1}$, and one
$\theta(1,2,3)$-block, namely $B_{2}$. Then let $B=B_{1}\cup B_{2}$ and
$G^{\prime}=G[V(G)\setminus\\{V(B-u)\\}]$. Clearly, $|V(B)|=6$ and $|E(B)|=7$.
So $V(H)=3l+2-5=3(l-1)$ and $|E(H)|\leq 5(l-1)-2=5l-7$. Hence
$|E(G)|=|E(B)|+|E(G^{\prime})|\leq 7+5l-7=5l<5l+1$. Similarly, if (i) and
(iii), or (ii) and (iii) occur simultaneously, we can similarly conclude that
$|E(G)|$ is less than $5l+1$, which contradicts the assumption.

Based on the analysis of the graph blocks in the three cases above, we have
directly proven this theorem. ∎

The characterization theorems for extremal 3-cactus graphs and 4-cactus graphs
are given here. The proof techniques of the following two theorems are similar
to Theorem 5. We leave the frustrating proof details to the reader.

######  Theorem 6.

Let $G$ be an extremal $3$-cactus with $n\geq 1$ vertices. The following
statements hold true.

  * (1)

If $n\equiv 0\pmod{4}$, then $G$ is obtallined by coalescing $\frac{n-4}{4}$
copies of $\theta(1,2,2,2)$ and one copy of $\theta(1,2,2)$.

  * (2)

If $n\equiv 1\pmod{4}$ and $n\neq 1$, then $G$ is obtained by coalescing
$\frac{n-1}{4}$ copies of $\theta(1,2,2,2)$; if $n=1$, then $G\cong K_{1}$.

  * (3)

If $n\equiv 2\pmod{4}$, then $G$ is either obtained by coalescing by
$\frac{n-2}{4}$ copies of $\theta(1,2,2,2)$ and a copy of $K_{2}$, or obtained
by coalescing $\frac{n-6}{4}$ copies of $\theta(1,2,2,2)$ and either one copy
of $\theta(2,2,3)$, one copy of $\theta(2,2,2,2)$, or one copy of
$\theta(1,2,2)$ and $K_{3}$.

  * (4)

If $n\equiv 3\pmod{4}$, then $G$ is either obtained by coalescing by
$\frac{n-3}{4}$ copies of $\theta(1,2,2,2)$ and a copy of $K_{3}$, or obtained
by coalescing $\frac{n-7}{3}$ copies of $\theta(1,2,2,2)$ and two copies of
$\theta(1,2,2)$.

######  Theorem 7.

Let $G$ be an extremal $4$-cactus with $n\geq 1$ vertices. The following
statements hold true.

  * (1)

If $n\equiv 0\pmod{3}$, then $G$ is obtained by coalescing $\frac{n-3}{3}$
copies of $K_{4}$ and one copy of $K_{3}$, or obtained by coalescing
$\frac{n-6}{3}$ copies of $K_{4}$ and one copy of $\theta(1,2,2,2,2)$.

  * (2)

If $n\equiv 1\pmod{3}$ and $n\neq 1$, then $G$ is obtained by coalescing
$\frac{n-1}{3}$ copies of $K_{4}$; if $n=1$, then $G\cong K_{1}$.

  * (3)

If $n\equiv 2\pmod{3}$, then $G$ is either obtained by coalescing by
$\frac{n-2}{3}$ copies of $K_{4}$ and a copy of $K_{2}$, or obtained by
coalescing $\frac{n-5}{3}$ copies of $K_{4}$ and either one copy of
$\theta(1,2,2,2)$, one copy of $\tilde{\theta}_{1}$, or one copy of
$\tilde{\theta}_{2}$.

##  5 Concluding remarks

In this article, we have made a start on the topic of “extremal” $k$-cactus
graphs. We give tight upper bounds on the sizes on $k$-cactus graphs for
$2\leq k\leq 4$. Moreover, the corresponding extremal graphs are also
characterized.

The next step would seem to be to look at $k$-cactus graphs for larger values
of $k$ (see also Problem 1). To be frank, for relatively smaller values of
$k$, such as $k=5$ or $6$, it can be handled by applying the similar approach
in this article. Patience is needed, but the level of complexity should not
increase too much. However, for larger or especially general values of $k$,
establishing (sharp) bounds is likely to be a difficult problem. It is worth
noting that we first characterize $2$-, $3$-, $4$-cactus graphs, and then give
upper bounds on their sizes. These characterizations heavily rely on the tool
of the ear decomposition. However, as the value of $k$ in $k$-cactus graphs
increases, similar characterizations become an increasingly difficult thing,
because the choices of adding ears will grow significantly (even when
considering symmetry). As a result, we might need to find some cleverer ways
to resolve these problems without using the ear decomposition theorem.

Fortunately, we can still roughly catch some potential strategies to tackle
the extremal problem on the general $k$-cactus graphs. From our theorems, it
appears that the primary constituents of extremal $k$-cactus graphs are
(2-connected) extremal nice $k$-cactus graphs with minimum order. Therefore,
for solving Problem 1, we may need to solve two preliminary problems below.

######  Problem 2.

What are the (tight) lower bounds on the orders of nice $k$-cactus graphs?

######  Problem 3.

What are the (tight) upper bounds on the sizes of $2$-connected nice
$k$-cactus graphs when $n\leq k+1$?

##  6 Acknowledgment

We claim that there is no conflict of interest in our paper. No data was used
for the research described in the article.

## References

  * [1] B. Ben-Moshe et al., Efficient algorithms for the weighted 2-center problem in a cactus graph, Lect. Notes Comput. Sci., 3827 (2005) 693–703.
  * [2] E.S. El-Mallah, C.J. Charles, The complexity of some edge deletion problems, IEEE Trans. Circuits Syst., 35 (1988) 354-362.
  * [3] P. Erdős, Elementary problem E3255, Amer. Math. Monthly, 95 (1988), 259.
  * [4] F. Harary, G.E. Uhlenbeck, On the number of Husimi trees: I, Proc. Natl. Acad. Sci. USA, 39 (1953) 315-322.
  * [5] L. Lovász, Combinatorial Problems and Exercises. Second Edition. North-Holland Publishing Co., Amsterdam, 1993.
  * [6] A. Rosa, Cyclic Steiner triple systems and labelings of triangular cacti, Scientia, 1 (1988) 87–95.
  * [7] S. Toida, Properties of a [sic] Euler graph, J. Franklin Inst. 295 (1973) 343–34.
  * [8] D.B. West, Introduction to Graph Theory (second edition), Prentice Gall, 2001\.
  * [9] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932) 150-168.
  * [10] Y. Xue et al., Fast searching on cactus graphs., J. Comb. Optim., 45 (2023) 22.