Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the vertices form a full graph.
Now, I cant get to prove it for the other option - i.e if every vertex in the tree is of degree $1\leq d(v) < n-2$ than the complement graph is connected.
 A: Assume that the graph is not connected. Then, separate the graph into 2 separate graphs. 
Now, all the missing edges between the 2 components must have belonged to the tree. 
Suppose the size of the 2 components is a and b. (size of a component refers to the number of vertices in it).
Then, we have :
$$
a + b  = n
$$
and
$$
a*b \le (n-1)
$$
(because the number of edges in a tree can't be more than that).
The only way this can happen is when a=n-1 and b=1 , which is the second part of your question.
A: The other answer is nice - this is just an alternative.
Let $T$ be a tree and $\overline{T}$ be its complement.  Suppose that in $\overline{T}$, there are vertices $a,b, c$ such that $a$ is not in the same component as $b$ and $c$, and that $b$ and $c$ share no edge.  Then $a,b,c$ form a triangle in $T$ and it cannot be a tree.  Thus $\overline{T}$ has at most 2 components $X$ and $Y$ and each must be a clique.  If both $|X|, |Y| \geq 2$, then take $x_1, x_2 \in X$ and  $y_1, y_2 \in Y$.  Then $T$ has the cycle $x_1y_1x_2y_2x_1$ and cannot be a tree.  So at least one of $X$ or $Y$ must be of size one, which is possible if $T$ is a star tree.
