self-complementary graph and cut vertex

by beta_me me_beta   Last Updated June 30, 2020 03:20 AM - source

I have difficulty understanding this '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.'

I narrowed down my argument to following : v be a cut vertex in the self-complimentary graph G. We partition N(v) into sets which do not share any edge. So, G'-v will have a complete multi-partite graph as a sub-graph. I'm not able to prove that the complete multi-partite graph will be actually a complete biclique.

Either I am wrong somewhere or missing some fundamental part. Please help out.

Reference : Part of the step in this problem here



Related Questions


Explain this proof of the 5-color theorem

Updated August 28, 2017 07:20 AM

Understanding proof for $e \leq 3v - 6$ in planar graphs

Updated September 03, 2017 03:20 AM