# 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$?

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.

• The above really helped a lot! However, since there's a bijection function $h: G_2 \to \bar{G_2}$, is it not better to write $deg_{G_2}(v) + deg_{\bar{G_2}}(h(v)) = n - 1$? – Shahin Nosrat Jogan Apr 23 '16 at 16:04
• @Shahin: No, because it’s not true; what is true is that $$\deg_{G_2}v+\deg_{G_2}h(v)=n-1\;.$$ – Brian M. Scott Apr 23 '16 at 21:25
• I'm having difficulty in interpreting the above equation. Since if we fix some $v \in G_2$ then by $h: G_2 \to \bar{G_2}$, we have $h(v) \in \bar{G_2}$, then the sum of that fixed $v \in G_2$ and it's image namely $h(v) \in \bar{G_2}$ should equal $n - 1$? If, my argument is still not true, then can you please explain! – Shahin Nosrat Jogan Apr 24 '16 at 9:29
• @Shahin: Fix $v\in G_2$, and let its degree in $G_2$ be $d$. The map $h$ is an isomorphism, between $G_2$ and $\overline{G_2}$, so it preserves degrees: the degree of $h(v)$ in $\overline{G_2}$ (not in $G_2$) is also $d$. That means that the degree of $h(v)$ in $G_2$ is $n-1-d$: the degrees of any vertex in $G_2$ and $\overline{G_2}$ must sum to $n-1$. Thus, $\deg_{G_2}v+\deg_{G_2}h(v)=n-1$. – Brian M. Scott Apr 24 '16 at 20:37