Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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.

share|improve this answer
1  
Surely you mean $a*b \leq n-1$? Slick answer though. –  Bambi Jun 25 at 9:25
    
@Bambi Thanks for the correction! :) –  Ojas Jun 25 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 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 at 9:50
    
Thanks. great proof! –  wannabe programmer Jun 25 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.