If $G$ is a self-complementary graph then, $G$ must have a vertex $u$ such that $G-u$ has a spanning biclique

130 Views Asked by At

If $G$ is a self-complementary graph then, $G$ must have a vertex $u$ such that $G-u$ has a spanning biclique.

To figure out a proof for the above, I visualize a contradiction. Suppose $G$ is a self-complementary graph and for any vertex $u$ in $G$, $G-u$ does not contain a spanning biclique. Since $G=\overline{G}$, we have $G-u=\overline{G}-u$. I was wondering if the second assumption in any way could be used to prove $G-u\ne \overline{G}-u$ due to some difference in number of edges, which would lead to a contradiction. However, I feel like I am unnecessarily complicating this and it is easier than it looks. Any help with the proof?

Edit: It is known that $G$ has a cut vertex $v$.

Note: This was required in this proof but I am stuck at the above claim.

1

There are 1 best solutions below

3
On BEST ANSWER

This seems false to me.

Consider the cycle $C_5$, its complement is also $C_5$, so it's self-complementary. However if we remove any vertex $u$, we get the path $P_4$, which is not spanned by a biclique (we can check that $P_4$ has neither $K_{1,3}$ nor $K_{2,2}$ as a subgraph, and there's no other bicliques that have the right number of vertices).

EDIT: If $G$ has a cut vertex, then so does $\overline{G}$. Let $u$ be a cut-vertex of $\overline{G}$. Let $H_1$ be one component of $\overline{G}-u$, and let $H_2$ be the union of all the other components of $\overline{G}-u$.

Since there are no edges between $H_1$ and $H_2$ in $\overline{G}$, we must have every possible edge between $H_1$ and $H_2$ in the original graph $G$. So $G-u$ has a spanning biclique with partite sets $V(H_1)$ and $V(H_2)$.