patternMinor
Calculate the number of cycles of a Cactus graph?
Viewed 0 times
numberthecactusgraphcalculatecycles
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#101082, answer score: 5
Revisions (0)
No revisions yet.