Let's have connected G(V,E) and disconnected G'(V,E') where |E|=|E'|. How can one proove G' always has at least the same number of cycles than G? I have 2 ideas how such a proof should look like.
Idea 1:
The intuition is that when "distributing" edges in a graph, to avoid cycles one aims for a tree until the graph becomes connected. This happens when the number of edges reaches v-1. Each "remaining" edge then creates a new cycle. This way we should end up with the least possible amouth of cycles.
Idea 2:
The intuition is that to create a connected graph from an arbitrary disconnected graph with the same number of edges, we need to repeatedly "move" an edge from some connected component so that it connects it with another connected component. We repeat until we get a connected graph.
Each such move either "breaks" some cycle or not.
If it does not, the number of cycles won't change. This is because connecting two connected components with an edge does not create a new cycle.
If it does, then the number of cycles in the graph decreases for the same reason. Therefore, at the end we end up with same or less number of cycles.
Is one of these a correct proof?
Best Answer
The claim is not true, let $G$ be $K_7$ with $21$ pendant vertices, it is a connected graph with $21 + 21 = 42$ edges and $28$ vertices. It has $\sum\limits_{i=3}^{7} \binom{7}{i}(i-1)!/2 = 1172$ cycles. On the other hand let $G'$ be the graph consisting of $7$ copies of $K_4$, it has $42$ edges and $28$ vertices, and it has $7(\sum \limits_{i=3}^4 \binom{4}{i}(i-1)!/2) = 7(7) = 49$ cycles.
I think the takeaway is this: If you have a large amount of edges packed close then the number of cycles explodes, and being connected or not doesn't really control this.