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$

1 Answer 1

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, 2013 at 8:53
  • $\begingroup$ not complete argument.What about if they are in the same component ? $\endgroup$
    – Frank
    Feb 28, 2017 at 10:33

You must log in to answer this question.

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