Question on Trees and Complements Are there any graphs such that the graph and its complement are both trees? 
I have come up with two examples so far, one with just a single node and the other which is $P_3$ (a tree with 3 edges). I'm not sure how to find every other one, or if there is a pattern here. I am supposed to first prove that a graph like this exists, then prove that there are no others other than the the ones I state. Thanks
 A: You got both of them.  As you found out yourself, this clearly won't work for two or three vertices, and the only way it works for 4 vertices is $P_4$ (Not $P_3$!) since the graph and its complement have $4\choose2$ $=6$ edges together and for them both to be a tree they need at least three edges, meaning that they both have exactly three edges, and for them to then both be trees it is then easy to verify there is only that one option. 
Finally, for $n\ge 5$ you get more than $n-1$ edges in either the grap or its complement, meaning that you will get a cycle and hence not both of them can be trees.
Put differently (and maybe a little nicer as a proof):
Since the graph and its complement both need to be trees, and since a graph with $n$ vertices is a tree iff it has $n-1$ edges, and since the graph and its complement have $n\choose2$ edges between them, we need to have:
$$2(n-1) = {n\choose2} = \frac{n(n-1)}{2}$$
Hence, 
$$4(n-1) = n(n-1)$$
Hence, $n=1$ or $n =4$
There is exactly one graph with 1 vertex, and it is easy to verify that the only graph with four vertices where its complement and itself are both trees is $P_4$
