# $G$ 3-connected graph, $xy \in E(G)$. $G'$ graph obtained from $G$ by removing the edge $xy$ and merging the vertices $x$ and $y$ into one vertex.

Let $$G$$ be a $$3$$-connected graph and $$xy \in E(G)$$. Let $$G'$$ be the graph obtained from $$G$$ by removing the edge $$xy$$ and merging the vertices $$x$$ and $$y$$ into one vertex. Prove: The graph $$G'$$ is $$3$$-connected if and only if the graph $$G -$${$$x, y$$} is $$2$$-connected.

Attempt:

I know that a graph $$G$$ is $$k$$-connected if it has at least $$k + 1$$ vertices and for every subset $$A \subseteq V(G)$$, $$|A| < k$$, the graph $$G-A$$ is connected.

Since $$G -$${$$x, y$$} is $$2$$-connected, removing any single vertex does not disconnect it. Now, I consider any subset $$A$$ of vertices in $$G'$$ such that $$|A| < 3$$ and I need to show that $$G' - A$$ is connected. How do I continue? Similarly I got stuck on the other implication. Any help would be appreciated.

## 1 Answer

Let the vertices $$x$$ and $$y$$ are merged into the vertex $$x$$.

$$(\Rightarrow)$$ The graph $$G-\{x,y\}$$ has at least $$3$$ vertices, because the graph $$G'$$ has at least $$4$$ vertices. Let $$A\subseteq V(G')-\{x,y\}$$ be any set such that $$|A'|<2$$ and $$v,u$$ be any distinct vertices of $$V(G)-(A\cup\{x,y\})$$. Since the graph $$G'$$ is $$3$$-connected there exists a path $$P$$ from $$v$$ to $$u$$ in $$G'$$ avoiding the vertices of $$A\cup\{x\}$$. Then $$P$$ is a path from $$v$$ to $$u$$ also in $$G$$ avoiding the vertices of $$A\cup\{x,y\}$$.

$$(\Leftarrow)$$ The graph $$G'$$ has at least $$4$$ vertices, because the graph $$G-\{x,y\}$$ has at least $$3$$ vertices. Let $$A'\subseteq V(G')$$ be any set such that $$|A'|<3$$ and $$v,u$$ be any distinct vertices of $$V(G')-A'$$.

Suppose that $$x\not\in A'$$. Since the graph $$G$$ is $$3$$-connected there exists a path $$P$$ from $$v$$ to $$u$$ in $$G$$ avoiding the vertices of $$A'$$. Replacing each maximal chain of consecutive vertices from $$\{x,y\}$$ in $$P$$ by $$x$$, we obtain a path $$P'$$ from $$v$$ to $$u$$ in $$G'$$ avoiding the vertices of $$A'$$.

Suppose that $$x\in A'$$. Since the graph $$G$$ is $$3$$-connected there exists a path $$P$$ from $$v$$ to $$u$$ in $$G$$ avoiding the vertices from $$A'\cup\{y\}$$. So $$P$$ is a path from $$v$$ to $$u$$ also in $$G'$$ avoiding the vertices from $$A'$$.