Prove cut-vertex $v$ in $G$ is not cut-vertex in $\overline G$

3.4k Views Asked by At

I'm trying to prove that if a vertex $v$ is a cut-vertex in a graph $G$, then $v$ is not a cut-vertex in $\overline G$.

So far, I have the following:

Let $v$ be a cut-vertex in $G$. Then, there are two vertices, $u$ and $w$ such that $v$ lies on every $u-w$ path in $G$.

Assume, to the contrary, that $v$ is a cut-vertex in $\overline G$ as well. Then, there are two vertices $u'$, $w'$ such that $v$ lies on every $u'-w'$ path in $\overline G$.

Since $v$ lies on every $u-w$ path in $G$, the edge $uw \notin E(G)$ and so $uw \in E(\overline G)$, so it follows that $\{u, w\} \neq \{u', w'\}$. Instead, either $\big|\{u, w\} \cap \{u', w'\}\big| = 1$ or $\{u, w\} \cap \{u', w'\} = \varnothing $.

We proceed by cases.

$\textbf{Case 1} \big|\{u, w\} \cap \{u', w'\}\big| = 1$.

Assume $u = u'$. As stated, $uw \in E(\overline G)$ which means that $ww' \notin E(\overline G)$, for otherwise, $u,w,w'$ forms a $u-w'$ path without $v$. But then, $ww' \in E(G)$. Also, $uw' \notin E(\overline G)$, and so $uw' \in E(G)$. Following the edge ${ww'}$ with $uw'$ gives us a $u-w$ path in $G$ without $v$ which is impossible.

$\textbf{Case 2} \{u, w\} \cap \{u', w'\}\ = \varnothing$.

Since ${u'w' \in E(G)}$, at most one of $u$ and $w$ can be adjacent to vertices $u'$, $w'$ in $G$, for otherwise we would have a $u-w$ path without $v$. Assume, $u$ is the vertex such that $uu', uw' \notin E(G)$. Then, $uu', uw' \in E(\overline G)$ which gives us a $u'-w'$ path in $\overline G$ without $v$ which is impossible.

Is there a simpler way to prove this result?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $v$ be a cut-vertex of $G$. To show $v$ is not a cut-vertex of $\bar{G}$, it suffices to show $\bar{G}-v$ is connected. Let $u,w\in V(G-v)$. The goal is to prove there is a $u-w$ path in $\bar{G}-v$.

As $v$ is a cut-vertex of $G$, $G-v$ has more than one connected component. The vertices $u,w$ are either members of the same connected component or in different connected components in $G-v$. If $u,w$ are in different connected components, then $uw\in E(\bar{G})$. Consider the case where $u,w$ are in the same connected component $P_1\subset G-v$. As $v$ is a cut-vertex, there must exist another connected component $P_2\subset G-v$. Let $z\in P_2$. As there are no edges between $P_1$ and $P_2$ under $G$, $z$ shares an edge with all vertices in $P_1$ under $\bar{G}$. Thus, there exists a $u-w$ path, namely $u-z-w$.