3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, I'm uncertain if my description of cactus graphs is accurate. For example, is a graph with two loops on a single vertex a cactus graph? It depends on the definition of cycle, but it seems so. In that case, a component of a cactus graph is homotopic to a bouquet of circles whose Euler characteristic is $1-c$ (also for $c=0$). This is the same result (choose $x=1$). In fact, every connected graph is homotopic to a bouquet of circles so this result is general, but then detecting cycles is a major focus of algebraic topology. $\endgroup$ – Derek Elkins Dec 6 '18 at 20:37

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.