Suppose the complement $\overline {G}$ of $G$ has size $\overline{m}$. Show that either $m >1/2 (nC2)$ or $\overline{m}>1/2(nC2)$

Question

Let $G$ be a graph of order $n$ and size $m$ such that $n=4k+3$ for some positive integer $k$. Suppose that the complement $\overline {G}$ of $G$ has size $\overline{m}$. Show that either $m >\frac{1}{2} (nC2)$ or $\overline{m}>\frac{1}{2}(nC2)$

Note: $nC2$ mean the combination $n$ choose $2$.

I tried to prove this bi contradiction. So I assume that $m \leq\frac{1}{2} (nC2)$ and $\overline{m}\leq\frac{1}{2}(nC2)$

Since $m \leq\frac{1}{2} (nC2)$,

$\overline{m} = (nC2)-m \geq (nC2)-\frac{1}{2} (nC2) =\frac{1}{2} (nC2)$

But I'm not sure this is going to get me anywhere.

Answer 1

Hints:

• $m+\bar m=N$ where $N=\displaystyle{n\choose 2}$
• Let $k$ be an integer, if $n=4k+3$ then $N=\displaystyle{n\choose 2}$ is odd
• Let $N$ be an odd integer, if $m\leqslant\frac12N$ and $\bar m\leqslant\frac12N$ then $m\leqslant\frac12N-\frac12$ and $\bar m\leqslant\frac12N-\frac12$ hence $m+\bar m\leqslant N-1$