Determine all the trees (on at least two vertices) which are isomorphic to their complement.
Hello graphed 4 trees and found onle two which are self-complementary ones. They are Tree with 1 vertex and 4 verteces. Is there general more self-complementary trees and if so , then is there a general rule for identifying them?
Thanks in advance!
Hint:
A tree on $n$ vertices always contains exactly $n-1$ edges. As a graph on $n$ vertices has $\binom{n}{2}$ possible edges total, this means that the complement of a tree on $n$ vertices always contains $\binom{n}{2}-(n-1)$ total edges.
But, if the tree is self-complementary, then necessarily its complement must also be a tree... which implies that $$ \binom{n}{2}-(n-1)=n-1. $$ This can only happen when $n=1$ (which is forbidden by your problem statement) or for $n=4$. So, you only need to try a very small number of trees.