# Cut sets in 2-connected 3-regular graphs?

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.

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$$.