7
$\begingroup$

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

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Just to be clear: $\displaystyle \binom{n}{2} = \frac{n(n-1)}{2}$. $\endgroup$ – ShreevatsaR Apr 22 '13 at 12:05
  • $\begingroup$ thanks sir. everything is clear now. $\endgroup$ – monalisa Apr 22 '13 at 12:14
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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