Tree complements
Task number: 4225
Find all trees \( T \) whose complement is a tree as well. Justify that you have not forgotten any.
Solution
Because for \( n = | V_T | \) it holds that \( n = | E_T | + 1 = | E _ {\bar T} | +1 \) and \( | E_T | + | E _ {\bar T} | = \binom{n}2 \), the number of vertices \( n \) must satisfy \( 2n-2 = \frac12 (n ^ 2-n) \), i.e. \( n^2-5n + 4 = 0 \). This quadratic equation has two nonnegative integer solutions:
- \( n = 1 \), the corresponding tree is \( K_1 \) and
- \( n = 4 \), the corresponding tree is \( P_4 \) (the other trees on the four vertices do not apply as we find out by case analysis).
