Graph Theory: Self - Complementary Graphs I have started reading Graphs and Digraphs by G Chartrand.
I'm stuck on the following problem:
Let $G_1$ and $G_2$ be self - complementary graphs, where $G_2$ has even order $n$. 
Now let $G$ be the graph obtained from $G_1$ and $G_2$ by joining each vertex of $G_2$ whose degree is less than $\frac{n}{2}$ to every vertex $G_1$. 
Show that $G$ is self - complementary.
I understand that a self - complementary graph $G$ is isomorphic to it's complement $G^{*}$.  
Where my difficulty lies is why every vertex of $G_2$ whose $deg_{G_2}(v) < \frac{n}{2}$ be joined to every vertex of $G_1$? 
I can't see the contradiction when $deg_{G_2}(v) = \frac{n}{2}$ is joined to every vertex of $G_1$?
 A: In order for $G$ to be self-complementary, you want to make sure that the construction joins the vertices of $G_1$ to exactly half of the vertices of $G_2$: when you take the complement, the vertices of $G_1$ will be joined to the other half of the vertices of $G_2$, so that you’ll have the same number of edges between the complements of $G_1$ and $G_2$ as $G$ has between $G_1$ and $G_2$. This is not by itself enough to ensure that $G$ is self-complementary, but it’s a good start.
Now $K_n$ has $\binom{n}2=\frac{n(n-1)}2$ edges. $G_2$ is self-complementary, so exactly half of those edges are in $G_2$, the other half being in the complement of $G_2$. This in turn means that the sum of the degrees of the vertices of $G_2$ must be $\frac{n(n-1)}2$, twice the number of its edges. Since $G_2$ is self-complementary, there is a bijection $h$ on its vertex set with the property that 
$$\deg_{G_2}v=\deg_{\overline{G_2}}h(v)=n-1-\deg_{G_2}h(v)$$
for each vertex $v$ of $G_2$, where $\overline{G_2}$ is the complementary graph. Clearly
$$\deg_{G_2}v<\frac{n-1}2\quad\text{ if and only if }\quad\deg_{G_2}h(v)=n-1-\deg_{G_2}v>\frac{n-1}2\;,$$
so the bijection $h$ pairs each vertex $v$ whose degree is less than $\frac{n-1}2$ with a vertex $h(v)$ whose degree is greater than $\frac{n-1}2$. It follows that half of the vertices of $G_2$ have degree less than $\frac{n-1}2$ and half have degree greater than $\frac{n-1}2$. 
Now note that since $n$ is even,
$$\deg_{G_2}v<\frac{n}2\quad\text{ if and only if }\quad\deg_{G_2}v<\frac{n-1}2\;,$$
and
$$\deg_{G_2}v\ge\frac{n}2\quad\text{ if and only if }\quad\deg_{G_2}v>\frac{n-1}2\;.$$
Thus, half of the vertices of $G_2$ have degree less than $\frac{n}2$, and the other half have degree greater than or equal to $\frac{n}2$.
In other words, the set of vertices of $G_2$ of degree less than $\frac{n}2$ at least has the right number of vertices; if we included the vertices of degree $\frac{n}2$, assuming that there are any, we’d have too many of the vertices of $G_2$ for the construction to work, because we’d have more than half of them.
For the proof that $G$ is self-complementary you can simply check that if $h$ is as above, and $k$ is an isomorphism from $G_1$ to its complement, then $h$ and $k$ together yield an isomorphism from $G$ to its complement.
