Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

1.4k Views Asked by At

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.

2

There are 2 best solutions below

5
On

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.

0
On

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.