5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.