alternative proof of graph property implying $3$ edge connectivity.

116 Views Asked by At

enter image description hereProblem:

If $G$ is a connected graph and for every edge $e$ there are cycles $C_1$ and $C_2$ such that $E(C_1) \cap E(C_2)=\{e\}$ then $G$ is $3$-edge connected.

Question: Is the following argument by contradicion correct? The solutions I know are direct solutions to the problem so any comments and complete answers to my question would be very uesful.

Suppose $G$ is not $3$-edge connected. Then we can disconnect $G$ by either removing one or two edges. Suppose the first case is true, so $G$ has a cut edge $e$. Then this edge can clearly not belong to any cycle, otherwise removing it would not change the fact that $G$ is connected. This contradicts the existance of cycles $C_1$ and $C_2$ containing $e$. So we can think about the second case. Let $e,e'$ be the edges that disconnect $G$. Note that by removing $e$ and $e'$, $G$ splits in exactly two connected components: Removing either $e$ or $e'$ does not disconnect $G$ by the argument before. So remove say $e$ then $e'$ becomes a cut edge in $G\setminus\{e\}$ hence $G \setminus \{e,e'\}$ has exactly two components $K_1$,$K_2$. Now Let $C_1$ be a cycle containing $e$. Then it is clear that the cycle must also contain $e'$ since this is the only way to get a path from one vertex of $e$ to the other, because they are in different components. But by this argument every cycle containing $e$ must also contain $e'$ wich contradicts the existence of cycles $C_1,C_2$ with $E(C_1) \cap E(C_2)=\{e\}$.

1

There are 1 best solutions below

2
On

Let $e=\{u,v\}$ and $e'=\{u', v'\}$. I see two gaps.

  1. Which components $u$ and $v$ are in: Since $G-\{e\}$ is connected and $G-\{e,e'\}$ is not, then we know that $u'$ and $v'$ are in two different components, but I don't see how we know if $u$ and $v$ are in the same component or not given the current information.

  2. The edges of $C_2$: If we assume that $e$ and $e'$ are both on cycle $C_1$, that does not imply both are on $C_2$.