1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$ – Shahin Nosrat Jogan Apr 23 '16 at 16:04
  • $\begingroup$ @Shahin: No, because it’s not true; what is true is that $$\deg_{G_2}v+\deg_{G_2}h(v)=n-1\;.$$ $\endgroup$ – Brian M. Scott Apr 23 '16 at 21:25
  • $\begingroup$ 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! $\endgroup$ – Shahin Nosrat Jogan Apr 24 '16 at 9:29
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 24 '16 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.