# 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.

-

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.

-
Surely you mean $a*b \leq n-1$? Slick answer though. – MightyJohnson Jun 25 '14 at 9:25
@Bambi Thanks for the correction! :) – Ojas Jun 25 '14 at 9:26
I have 2 problems with this proof: 1. how can you know for sure that the graph has only 2 components? 2. I didn't understand how you got the $a*b \leq n-1$ – wannabe programmer Jun 25 '14 at 9:39
All the edges between the 2 components must belong to the tree as they don't belong to the complement graph. The number of such edges would be $a*b$ . As a tree with $N$ vertices can't have more than $N$-1 edges, this number should be $\le (N-1)$. About your first doubt, if you have more than 2 components, the problem further increases ( the number of edges between the components would now be even more and always be more than N-1). – Ojas Jun 25 '14 at 9:50
Thanks. great proof! – wannabe programmer Jun 25 '14 at 10:07

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.

-