# Trees whose complement is also a tree

I am searching for those graphs $G$ where $G$ is a tree and its complement is also a tree. I came out with one such graph $P_4$. Are there any other too? I am not getting any other example. thanks

The one you found is unique, except for the graph on one vertex.

Consider the following two facts:

• A tree on $$n$$ vertices has $$n-1$$ edges,

• For a set of $$n$$ vertices, there are $$\binom{n}{2}$$ (unordered) pairs, so the complement of some graph with $$m$$ edges has $$\binom{n}{2} - m$$ edges.

So, if you have a tree on $$n$$ vertices, for its complement to also be a tree, you need $$\binom{n}{2} - (n-1) = (n-1)$$ edges, which gives $$n(n-1) = 4(n-1)$$. This can happen if either $$n = 1$$ (the graph of one vertex is its own complement, and can be called a tree), or else $$n = 4$$.

Now we can exhaustively try all possible trees on $$4$$ vertices (say $$A, B, C, D$$). There are only two of them, upto isomorphism: the path A—B—C—D (whose complement is indeed a tree), or the tree where $$A$$ is connected to each of the other three, whose complement is a triangle and not a tree.

• Just to be clear: $\displaystyle \binom{n}{2} = \frac{n(n-1)}{2}$. Apr 22, 2013 at 12:05
• thanks sir. everything is clear now. Apr 22, 2013 at 12:14

The graph on one node is a further (trivial) example. We see that no other graph on two, three or four nodes satisfies the condition.

In order to avoid $3$-cycles in the complement, every vertex needs to be connected to all but possibly one other vertex. If a tree $T$ has $n$ nodes, this means $n-2$ connected nodes.

So pick an arbitrary vertex $v$ in a tree $T$ on at least five nodes; it is connected to at least three other vertices $w_1,w_2,w_3$. But now look at the triple $w_1,w_2,w_3$. At least one of the possible edges needs to be occupied, otherwise there will be a cycle in the complement $T^c$ of $T$. However, any such edge would create a cycle in $T$. Thus $T$ doesn't satisfy the condition.

In conclusion, there can only exist such trees with $4$ or fewer nodes. We have listed those, and are done.

• +1, this is nice... it reminds me of the theorem on friends and strangers that proves $R(3,3) = 6$ ("at any party with at least 6 people...") Apr 22, 2013 at 12:28

Here is an alternative proof. If $n=1$ we are done, otherwise $n \geq 2$.

Any tree with at least two vertices has at least two leafs. Then the complement has at least two vertices of degree $n-2$.

Since the complement is also a tree, it has at least two vertices of degree $n-2$ and at least $2$ leafs. Then, the sum of those four degrees is

$$2(n-2)+2=2(n-1)$$

But by the Hanshaking Lemma the sum of all degrees is $2(n-1)$. Thus, (since the graph is connected) there cannot be any other vertex in the tree.

This shows that $n=4$, and the tree must have two vertices of degree $1$ and two vertices of degree $4-2=2$. It is easy to argue that this tree is $P_4$.