/sci/ - Science & Math

Struggling with a simple graph theory proof. It seems a little much for /mlg/ or /sqt/ but the folks here will probably be able to prove it

Let a simple graph [math]G=(V,E)[/math] be bipartite,

(i.e., there exists a choice of sets [math]X \subseteq V[/math], and [math]Y /subseteq V[/math] such that for every element of our edge set [math]E[/math], [math]e \in E[/math] is composed of [math]x \in X[/math] and [math]y \in Y[/math])

and that [math]G[/math] is also self-complementary,

(i.e., [math]G \cong G^c[/math], i.e., G is isomorphic to its complement)

Show that G must be such that [math]|X| \leq 2 [/math] AND [math]|Y| \leq 2 [/math]

Essentially, you can't have a bipartite and self-complementary simple graph on more than 4 vertices. Sorry for the long proposition, I'm having fun with latex.

My best approach is trying via contradiction, i.e., assume a G has ALL of the desired properties (simple, bipartite, self-complementary) and that its respective bipartitions have orders of larger than 2. So I list the vertices, i.e., [math]v_1, ... , v_x[/math], and [math]v_x+1, ... , v_y[/math]

But I don't quite see how it leads to a contradiction. Does it have something to do with the fact that self-complementary graphs also need to have vertices in multiples of 4? (something we showed earlier in the assignment)

Hello, /sci/. I want to be intelligent and smart as you. What I must do?