Let $G$ be a biconnected graph, $\{x,y\} \subseteq V(G)$ be a separator. Show that if $e=\{x,y\} \in E(G)$, then $G\backslash e$ is biconnected.

43 Views Asked by At

Let $G$ be a biconnected graph, let $w,z \in V(G)$ and $e=\{x,y\} \in E(G)$.

Here's my try:

It will be shown that, there are two internally distinct paths joining vertices $w,z$ (so $G\backslash e$ is biconnected).

As $G$ is biconnected, there are two internally distinct paths connecting the vertices $w,z$, let $P,Q$ be those.

Case $\textbf{1}$: $w,z$ belong to different connected components of $G\backslash e$.

It's true that $e \notin E(P)\cup E(Q)$. Indeed, since $P,Q$ are internally distinct,

e $\in E(P)\cup E(Q) \Rightarrow e \in E(P) \veebar e \in E(Q)$ .

Then, removing it would affect only $1$ path, the path to which edge $e$ belonged. Therefore, the vertices would continue to belong to the same connected components, contradiction.

We have nothing to prove, since removing $e$ does not affect either of the two internally distinct paths.

Case $\textbf{2}$: $w,z$ belong to the same connected component of $G\backslash e$.

Let $X,Y$ be two connected components of $G\backslash e$.

  • If $e \notin E(P)\cup E(Q)$ we have nothing to prove, since, in this case, the two internally distinct $(w,z)$-paths are not affected by the removal of edge $e$.
  • If $e \in E(P)\cup E(Q)$ ?

I considered a vertex $u$ in some other connected component of $G\backslash e$, but couldn't find two internally distinct paths joining vertices $w,z$.

Any help would be greatly appreciated.