Show that joining of 2 self complement graph is another self complement graph.

253 Views Asked by At

Let $G_1$ and $G_2$ be self-complement graphs, where $G_2$ has even order $n$. Let $G$ be the graph obtained from $G_1$ and $G_2$ by joining every vertex of $G_2$ whose degree is less than $\frac{n}{2}$ to every vertex in $G_1$. Show that $G$ is self-complement.

here is what I got so far

Since $G_1$ and $G_2$ be self-complement graphs, $G_1 \cong \overline{G_1}$ and $G_2 \cong \overline{G_2}$. Half of number of vertices in $G_2$, which will be an even number since $n$ is even, will connect to every vertex in $G_1$.

Since $G_1 \cong \overline{G_1}$ and $G_2 \cong \overline{G_2}$. Should I say Half of number of vertices in $G_2$, which will be an even number since $n$ is even, will connect to every vertex in $\overline{G_1}$? I'm kinda stuck here.

1

There are 1 best solutions below

0
On BEST ANSWER

Since $G_2 \cong \overline{G_2}$, we have that they have the same degree sequense, so the number of nodes with degree inferior to $(n-1)/2$ is equal to the number of ones with degree superior to it, and the congruence brings the ones into the others.

The congruence of the two graphs do all the rest of work: if one node in $G_2$ is connected to all the nodes of $G_1$, then the correspondent node in $\overline {G_2}$ is connected to all the nodes of $\overline{G_1}$, and viceversa, so this confirms that $G$ is congruent to his complementary