Let $G$ and $H$ be two self complimentary graphs with with disjoint vertex sets, where H has even order n. Let F be the graph obtained from $G \cup H$ by joining each vertex in G to every vertex of degree less than $\frac{n}{2}$ in $H$. Show that $G \cup H$ is selfcomplimentary.
My Attemp at proof so far: We consider $\overline{G \cup H}$, to do so we consider $G$ and $H$ seperately. Since $G \cong \overline{G}$
and $H \cong \overline{H}$ we know that each connected component is self complementary and so we must now consider the connections between the 2 components. We know that a self complimentary graph has exactly $\frac{1}{2}\binom{n}{2}$ edges, with exactly $\frac{n}{2}$ vertices above and below degree $\frac{n}{2}$. This implies that there is exactly the same number of connecctions between $G$ and $H$ as there are between $\overline{G}$ and $\overline{H}$.
From here i'm not completely certain where to go, any help is appreciated!
Best Answer
Let $\varphi$ be the isomorfism $\varphi: G\rightarrow \overline G$ and let $\theta$ be the isomorphism $\theta:H\rightarrow \overline H$.
Consider the function $\sigma: F\rightarrow \overline F: f(v)=\left\{ \begin{array}{ll} \varphi(v) & v\in G \\ \theta(v) & v\in H \end{array}\right .$
We have to show that $\sigma(uv)$ is not an edge of $F$ if and only if $uv$ is not an edge of $F$ ( this would prove $\sigma$ is an isomorphism).
We clearly only need to check the case $u\in G$ and $v\in H$.
Notice that $d(\theta(v))$=n-d(v)-1$ for all $v\in H$. So we have:
$uv\in F \iff d(v)<n/2\iff n/2<n-d(v)\iff n/2\leq n-d(v)-1=d(\theta(v))\iff \varphi(u)\theta(v)\not\in F\iff \sigma(uv)\not \in F$