How much does the number of connected components of a graph grow in the case below?

Question

Let $G=(V,E)$ be a simple graph with $c$ connected components. We say that $e_1, e_2 \in E$ is inseparable if the fundamental cycles of $e_1$ and $e_2$ are identical in a given fundamental cycle basis. I would be curious whether all cycles of $e_1$ and $e_2$ are identical in this case. I think that inseparability is an equivalence relation (please, corroborate it or give me a counterexample), whose cells are called inseparability classes. Let $I$ be an inseparability class and suppose that the edges in $I$ can be decomposed into $c_I$ connected components. I state that $G_I=(V,E\setminus I)$ contains $c+c_I-1$ connected components, but I do not know how to (dis)prove. Could you please help me to solve this problem?

Answer 1

I would be curious whether all cycles of $e_1$ and $e_2$ are identical in this case.

Interesting question, but I'm not sure how it relates to the question in the title or below.

I think that inseparability is an equivalence relation (please, corroborate it or give me a counterexample)

Let $B = \{C_1, C_2, \ldots, C_n\}$ be a fundamental cycle basis and suppose $e_1$ is in each of $\{C_1, C_2, \ldots, C_m\}$, with $m \leq n$. Say $e \sim f$ if $e$ and $f$ have the same set of fundamental cycles. Clearly $e_1 \sim e_1$, and if $e_1 \sim e_2$, then $e_2 \sim e_1$. Transitivity isn't much harder to check.

I state that $G_I=(V,E\setminus I)$ contains $c+c_I-1$ connected components, but I do not know how to (dis)prove.

It's not true the way you have it stated now, because of the difference between graph components and matroid components. You may want to revise your hypothesis in terms of graph blocks, or start with a $2$-connected graph.

Consider, for instance, a cactus graph consisting of a $5$-cycle and five triangles, where each triangle is incident with one vertex of the $5$-cycle. This graph has a unique fundamental cycle basis. If $e$ is an edge of the inner $5$-cycle, then its inseparability class $I$ is the entire cycle. So the graph $(V, E \backslash I)$ has $5$ components, but $c + c_I - 1 = 1 + 1 - 1 = 1$.