Cut sets in 2-connected 3-regular graphs?

Question

I believe that I have a result that is well known by someone here. If you know where I can find a proof, then I would appreciate it. It seems like elementary graph theory, but I have not been able to find it or prove it myself.

Here is the set-up. Let $n$ be a positive integer and let $G$ be a 2-connected, cubic (3-regular), undirected multigraph with vertex set $\{1,2,3,...,2n\}$. Thus, $G$ has precisely $3n$ edges, no bridges, but it might have a cut set with only 2 edges. Next, suppose $T$ is a spanning tree of $G$. Then the complement $G\backslash T=\{e_0,e_1,e_2...,e_n\}$ consists of precisely $n+1$ edges. For each edge $e_i\in G\backslash T$, there is a unique cycle, say $\gamma_i$, in $T\cup e$. Define a function $f$ from the edge set $E(G)$ to the power set $\mathcal{P}(\{0,1,2,...,n\})$ as $$f(e)=\{i\in\{0,1,2,...,n\}: e \in \gamma_i\}.$$ Thus, $f$ tells which which cycles among $\{\gamma_0,\gamma_1,\gamma_2,...,\gamma_n\}$ pass through a given edge.

With this set-up, here is my observation: Such a graph appears to be 3-connected if and only if $f$ is one-to-one. That is, given a graph $G$, one can detect a 2-edge cut set exactly when there are two edges $e_1$ and $e_2$ that have the same cycle assignments. The choice of the spanning tree used to define $f$ seems to be irrelevant as far as this goes. That is, the function $f_T$ always seems to detect the same 2-edge cut sets for any choice of $T$.

(I should add that this observation seems to hold for multigraphs that are not 3-regular, if only 2-connected. For my purposes, however, I only care about 3-regular graphs.)

Do you know how to prove or disprove this observation? If you can point me to a reference, then I would appreciate it.

Answer 1

For any connected graph $G$ and spanning tree $T$ this collection of $\{\gamma_i: 0 \leq i \leq n\}$ form a basis of the cycle space known as a fundamental cycle basis. This means every Eulerian subgraph, and in particular every cycle, in $G$ can be expressed as the symmetric difference of some of the $\gamma_i$. Notice that $f(e) \neq \varnothing$ for any $e$ by the $2$-edge-connected assumption.

Assume $f$ is one-to-one. If we remove two edges not in $T$, then the graph is certainly still connected. If we remove two edges both in $T$, then the graph is still connected because we can bypass each edge with a different cycle by the assumption that $f$ is one-to-one. Let $e,e' \in T$ be the two edges. When there is a fundamental cycle in $f(e)$ which is not in $f(e')$ and conversely it is clear which cycles to pick. Otherwise $f(e)$ is a proper subset of $f(e')$. In this case we pick $\gamma \in f(e') \setminus f(e)$ to bypass $e'$ and take the symmetric difference of $\gamma$ with some element of $f(e)$ and extract a cycle containing $e$ but not $e'$ which we use to bypass $e$. If we remove one edge from $T$ and one edge not from $T$, then also the graph will be still connected. If $e$ is the edge not in $T$ then $f(e) = \{\gamma_i\}$ for some $i$. If $e'$ is the edge in $T$ then $f(e') \neq \{\gamma_i\}$ by the one-to-one assumption and $f(e') \neq \varnothing$ by the $2$-edge-connected assumption. Thus we can connect any two vertices by following $T$ and bypassing $e'$ with $\gamma_j \in f(e')$ with $\gamma_i \neq \gamma_j$ (and thus $e \not\in \gamma_j$).

Assume $f$ is not one-to-one and that $f(e) = f(e')$. Since every cycle is the symmetric difference of some of the $\gamma_i$ this means every cycle either contains both $e$ and $e'$ or it contains neither. This implies the removal or $e$ and $e'$ disconnects $G$.