Prove that if two graphs, $G$ and $\overline{G}$, are isomorphic, the number of nodes cannot be twice an odd number.

discrete mathematicsgraph theorygraph-isomorphism

Having a really hard time going about proving this.

First, Graph $G$ is constructed by having $n$ nodes and joining some pairs of distinct nodes with at most one line.

Second, Graph $\overline{G}$ is constructed by having the same $n$ nodes as Graph $G$ but instead joining two nodes with a line if and only if they were not joined in $G$.

From what I gathered, Graphs $G$ and $\overline{G}$ can look like below if $n=4$:
enter image description here

How would I go about proving that if Graphs $G$ and $\overline{G}$ are isomorphic then $n$ cannot be twice an odd number (6, 10, 14 …)?

Best Answer

By way of contradiction, suppose that $|V(G)|=2(2n-1)=4n-2$ for some $n\in\mathbb{N}$.

Let $T$ be the total number of edges possible. This value is is

$$T=\frac{(4n-2)(4n-3)}2=\frac{16n^2-20n+6}{2}=8n^2-10n+3$$

Since $T$ is odd, and $|E(G)|+|E(\overline{G})|=T$, it can never be the case that $|E(G)|=|E(\overline{G})|$. Thus $G\ncong\overline{G}$.

Related Question