A nontrivial tree such that its complement is a maximal planar graph A nontrivial tree $T$ of order $n$ has the property that its complement $\overline{T}$ is a maximal planar graph (i.e., a planar graph such that adding any edge makes it nonplanar).
(a) What is $n$?
(b) Give an example of a tree $T$ with this property.
I already figured out that $n$ has to be $7$, but I'm having trouble thinking of a graph that works for this.
 A: I have found a tree for which the complement is maximal planar and the order is 7 (of course the order must be 7, as you have already discovered.)  I started backwards by finding a maximal planar graph with at least 2 vertices of degree 5 (to satisfy the leaves).  Here is the graph of the complement:

And here is the graph whose complement is maximal planar and pictured above.
  
I'm not 100% sure that this is the unique solution.  There could be more, but I think with a little work I could prove this is the unique solution.  I apologize for the sucky drawings as well.
EDIT:
I should also note that for all this to work, we need to not only assume its a non-trivial tree, but also that $n \ge 3$.  This is due to the fact that maximal planar graphs require $n\ge 3$.  If not, then the theorem "If $G$ is a maximal planar graph, then $\delta (G) \ge 3$" holds no water.  ( as well as many more results).  I raise this concern since $n=2$ appears to be a solution to the required number of vertices that are roots of the polynomial $n^2-9n+14$.
