1
$\begingroup$

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 !

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.