A Self Complementary Graph has a cut vertex iff it has a vertex of degree $1$

Question

Probably this question was posted earlier here and no answer was given , also I have different point of doubt in my answer(different from him), so I'm posting this question.

Solution begins like:

For the converse , let $v$ be a cut vertex in a self complementary graph $G$. The graph $G − v$ has a spanning biclique, meaning a complete bipartite subgraph that contains all its vertices.

Since $G$ is self complementary, also $G$ must have a vertex $u$ such that $G − u$ has a spanning biclique.

Since each vertex of $G − v$ is nonadjacent to all vertices in the other components of $G − v$, Upto here it is fine .. i am getting it but i am not able to visualise the furthur points.

Since each vertex of $G − v$ is nonadjacent to all vertices in the other

components of $G − v$ , a vertex other than $u$ must be in the same partite set of the spanning biclique of $G − u$ as the vertices not in the same component as $u$ in $G − v$. Hence only $v$ can be in the other partite set, and $v$ has degree at least $n − 2$. We conclude that $v$ has degree at most $1$ in $G$, so $G$ has a vertex of degree at most $1$. Since a graph and its complement cannot both be disconnected, $G$ has a vertex of degree $1$.

Please help me out!! Thank you !

Answer 1

Let $H$ and $K$ be the partite sets of the bipartition of $G-u$. Let $w$ be a vertex different from both $u$ and $v$; without loss of generality we may assume that $w\in H$. Now remember that $v$ was a cut vertex of $G$, so that $G-v$ has at least two components. Let $C$ be the component of $G-v$ that contains $w$.

Suppose that $x$ is a vertex of $G-v$ that is not in $C$. Then there is no edge between $w$ and $x$ in $G-v$, since there are no edges between different components of $G-v$. This means that there is no edge between $w$ and $x$ in $G$, since removing $v$ from $G$ would not have affected such an edge. $H$ and $K$ are the partite sets of a spanning biclique for $G-u$, so if $x$ were in $K$, $G-u$ would have an edge between $w$ and $x$, and hence so would $G$. We just saw that this is not the case, so $x$ cannot be in $K$ and must therefore be in $H$. This shows that every vertex of $G-v$ that is not in $w$’s component $C$ of $G-v$ must belong to the partite set $H$, the one that contains $w$.

Now what about a vertex $x$ of $G-v$ that is in $C$ (but isn’t $w$)? Let $y$ be any vertex of $G-v$ that is not in $C$. There is no edge in $G-v$ between $x$ and $y$, since they are in different components, and since neither of them is $v$, there is no edge between them in $G$, either. But then there is no edge between them in $G-u$, which means that they must be in the same partite set of the spanning biclique. We just showed that $y$ is in $H$, so $x$ is also in $H$.

We have now shown that every vertex of $G-u$ that is also in $G-v$ must belong to $H$, the same partite set that contains $w$. On the other hand, $K\ne\varnothing$. The only vertex of $G-u$ that isn’t in $G-v$ is $v$ itself, so $v$ must be the one vertex in $K$: $K=\{v\}$, which implies that $v$ is adjacent to every vertex in $H$. $H$ contains every vertex of $G-u$ except $v$, so $|H|=n-2$, and therefore $\deg_Gv\ge n-2$. But then

$$\deg_{G'}v=(n-1)-\deg_Gv\le(n-1)-(n-2)=1\;:$$

$v$ has degree at most $1$ in $G'$. Since $G$ is self-conjugate, $G$ also has some vertex of degree at most $1$.

Finally, if $\deg_{G'}v$ were $0$, $G$ would also have a vertex of degree $0$, so neither $G$ nor $G'$ would be connected. This, however, is impossible: for any graph $G$, at least one of $G$ and $G'$ is connected. Thus, $\deg_{G'}v=1$, and $G$ also has a vertex of degree $1$.