1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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:

enter image description here

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:

enter image description here

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

$\endgroup$
2
  • $\begingroup$ I don't know how to show those properties of $G'$ can you please show me how? $\endgroup$ Oct 10 '13 at 8:53
  • $\begingroup$ not complete argument.What about if they are in the same component ? $\endgroup$
    – Frank
    Feb 28 '17 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.