Prove that if $v$ is a cut-vertex of a connected graph $G$, then $v$ is NOT a cut vertex of $G'$.
I know that a vertex $v$ is a cut vertex of $G$ IFF there exists vertices $u$ and $w$ $(u,w \not=v)$ such that $v$ is on every $u-w$ path of $G$.
I also know that the complement $G'$ of a graph $G$ is a graph with vertex set $V(G)$ such that two vertices are adjacent in $G'$ IFF they are NOT adjacent in $G$.
So is it correct to conclude that there are no $u-w$ paths in $G'$ on which $v$ is found?
I don't know how to set up this proof
Best Answer
By definition of a cut vertex, $G \setminus \{v\}$ has more components than $G$. Let $X$ be one of these components. Let $Y$ be $G \setminus \{v\} \setminus X$. This is illustrated below:
Since $X$ is a connected component of $G \setminus \{v\}$, there are no edges from $X$ to any vertex in $Y$ (otherwise this vertex would also be in $X$). Hence, in $G'$, every vertex of $X$ is connected to every vertex in $Y$. We illustrate this subgraph of $G'$ below:
Both $X$ and $Y$ exist and are non-empty (since $v$ is a cut vertex). We see that $G' \setminus \{v\}$ has one component (any pair of vertices is connected via a path of the form $x_i y_j$ or $x_i y_1 x_j$ or $y_i x_1 y_j$).
If $v$ were a cut vertex of $G'$, then $G' \setminus \{v\}$ would have more components than $G'$ (which has at least one component, since it contains the vertex $v$), but $G' \setminus \{v\}$ has only one component, giving a contradiction. Hence $v$ is not a cut vertex of $G'$.