4
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .