112k views
0 votes
How many trees are there whose complement is also a tree?

User Atirag
by
8.6k points

1 Answer

6 votes
There is only one tree whose complement is also a tree. Using the graph theory and discrete mathematics we can prove this.
First, consider that for a tree that has n vertices, the number of edges is (n - 1)
Next, for n vertices, there are n(n - 1)/2 unordered pairs.
To find the complement of the tree, this equation must hold true:
n(n - 1)/2 - (n - 1) = (n - 1)
Simplifying
n(n -1) - 2(n - 1) = 2(n - 1)
n² - n - 2n + 2 - 2n + 2 = 0
n² - 5n + 4 = 0
Solving the quadratic equation
n = 1 and 4
A tree can't be on a vertex of only 1. So the only applicable number of vertices is 4. So, there can only be one true whose complement is a tree.
User Oluwasegun Wahaab
by
8.3k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories