graph theorytrees
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!
You're essentially asking for the number of non-isomorphic trees on $4$ vertices. Here they are:
We can verify that we have not omitted any non-isomorphic trees as follows.
The total number of labelled trees on $n$ vertices is $n^{n-2}$, called Cayley's Formula. When $n=4$, there are $4^2=16$ labelled trees.
The number of labelled graphs isomorphic to a graph $G$ is given by $$\frac{n!}{|\mathrm{Aut}(G)|}$$ where $n$ is the number of vertices of the graph, and $\mathrm{Aut}(G)$ is the automorphism group of the graph. This is a consequence of the Orbit-Stabiliser Theorem. In the above two cases, the automorphism groups have size $6$ (and is isomorphic to $S_3$) and $2$, respectively.
So the $16$ labelled $4$-vertex trees partition into $24/6=4$ trees isomorphic to the tree on the left and $24/2=12$ trees isomorphic to the tree on the right. Since $16=4+12$, we have accounted for all isomorphism classes of trees.
(Note: more than half of the labelled $4$-vertex trees are isomorphic to the graph on the right.)
You know that in your graph $G$ with each vertex of degree at least $k$ there exists a subgraph isomorphic to the tree $T_{k}$. All we need now is one more vertex in $G$ to tack onto $T_k$ which isn't already contained in $T_k$.
Examine the vertices adjacent to some end-point $t$ of the tree $T_k$. How do we know that there must be a vertex adjacent to $t$ not contained in $T_k$?
Best Answer
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.