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

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

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