8
$\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$

3 Answers 3

18
$\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$
2
  • 1
    $\begingroup$ Just to be clear: $\displaystyle \binom{n}{2} = \frac{n(n-1)}{2}$. $\endgroup$ Apr 22, 2013 at 12:05
  • $\begingroup$ thanks sir. everything is clear now. $\endgroup$
    – monalisa
    Apr 22, 2013 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$
1
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .