Calculate the number of cycles of a Cactus graph?

Question

Considering a cactus graph $G = (V, E)$, defined as:

A graph is a cactus if every edge is part of at most one cycle.

There is a way to calculate the number of cycles in this graph given only $n= |V|$ and $m = |E|$?

I did some examples before posting this, but now I think I got somewhere. If $G$ is connected, $m = n-1$ results that $G$ is a tree (we can not have less as $G$ will be disconnected). If $m > n-1$, then the number of cycles is equal to $m - n + 1$.

If $G$ is not connected, then we can take each connected component $C_{1}, ..., C_{k}$ and deal with them as a separated cactus graphs and then the number of cycles in the original graph is $\sum_{i=1}^{k} cycles(C_{i})$, where $cycles(H)$ is the function described above and $H$ a connected cactus graph.

Intuitively, I think that is because each edge added create exactly one cycle, as adding more than one cycle goes against the definition of the cactus. And to add a edge without adding a cycle you must connect a vertex that was previous isolated, not changing $m - n + 1$.

But I am not sure how to formalize this now.

Answer 1

If a graph is a cactus, then the number of cycles is $c = m-n+x$, where $x$ is the number of connected components and $c$ is the number of cycles.

The proof is by induction on the number of edges. If $m = 0$, then the graph contains no cycles, and furthermore $n = x$, and so $m-n+x = 0$.

Suppose now that $m > 0$, and remove an arbitrary edge $(u,v)$. There are two cases:

• The edge was not on a cycle. In that case, removing the edge increases the number of connected components by one: otherwise, $u,v$ are connected by some simple path not involving $(u,v)$, which together with $u,v$ would form a cycle. Therefore by the induction hypothesis, the number of cycles in the new graph is $(m-1)-n+(x+1) = m - n + x$. Since the original graph has the same number of cycles by assumption, this proves the induction hypothesis in this case.

• The edge was part of a unique cycle. In this case, removing the edge does not increase the number of connected components, since $u,v$ are connected by the rest of the cycle. By the induction hypothesis, the new graph has $(m-1)-n+x = m-n+x-1$ cycles. The original graph has one more cycle, for a total of $m-n+x$ cycles, proving the induction hypothesis in this case as well.

Answer 2

Another proof of the statement from Yuval Filmus' answer.

Using the algebraic topology based techniques that I briefly describe in this answer, we can reason as follows.

$n-m$ is the Euler characteristic (for any graph). A connected component of a cactus is either a tree, in which case its Euler characteristic is $1$, or it's cycle with some trees hanging off it, in which case its Euler characteristic is $0$. The Euler characteristic for the whole graph is the sum of the Euler characteristic of the components. Therefore the Euler characteristic of the whole graph is the number of connected components minus the number of cycles, i.e. $x-c=n-m$ using the variables from Yuval Filmus' answer.