How to prove that if a graph and its complement graph are trees then there're $4$ vertices in the vertex set of the graphs?

Question

Let $G=(V,E)$ be a simple graph with at least $2$ vertices. Let $G'=(V, E')$ be the complement graph of $G$. Prove that if $G$ and $G'$ are trees then $|V|=4$.

According to the property of trees in $|E|=|E'|=|V|-1$. That is both graphs have the same number of edges. Also a complete graph $K_n$ will have $\frac{n(n-1)}{2}$ edges and by definition of complement graph $|E|=|E'|=\frac{n(n-1)}{4}$.

Check if the conditions hold in case $|V|=4$: $$ \frac{4\cdot 3}{4}=3\quad\text{and also }4-1=3 $$ For $|V|=5$: $$ \frac{5\cdot 4}{4}=5 $$ but $|E|$ must be $5-1=4\neq 5$. Indeed for any $n\neq 4$ we have: $$ \frac{n(n-1)}{4}\neq n-1 $$

I just wonder if my proof is ok and all the transitions are correct.

Answer 1

You started very good, and arrived soon to both sides of the equation we want to hold: $$\frac{n(n-1)}4=n-1$$ As $n\ne1$ is assumed, we can divide by $n-1$, then multiply by $4$, and arrive to $n=4$.

Answer 2

Yes, you are correct. Maybe you should emphasize that here the number of vertices $n$ is at least $2$ otherwise we should also consider the case of $n=1$.

By definition $|E|+|E'|=\frac{n(n-1)}{2}$ and since $E$ and $E'$ are trees then $|E|=|E'|=n-1$. Hence $$2(n-1)=|E|+|E'|=\frac{n(n-1)}{2}\stackrel{n\not=1} {\implies}2=n/2\implies n=4.$$