How many edges can you add to a tree with $n$ vertices so it stays planar?
My attempt:
Any planar graph has $|E|\le 3n-6$, and tree has $n-1$ edges, so we can add at most $2n-5$ edges.
I tried a lot of examples, and I was always able to add exactly $2n-5$ edges no matter in which order I placed them. But I am stuck without proof.
Thanks to JMoravitz, I think I got it. Suppose That for each $n-1$ tree, we can add $2n-7$ edges. Now we take any $n$ tree and pick any leaf (which exists for any tree with $n>0$). We remove this leaf (or just pretend it doesn't exist) and add 2n-7 edges (which we can do by hypothesis).
Now in this new graph with $n-1$ vertices and $2n-7$ edges, each face is incident to exactly $3$ vertices, if they were perhaps incident to $4$ vertices, we could just add an edge between $2$ which aren't connected, which would be a contradiction.
Finally we add back the leaf that we removed, which now lives on a face that is incident to his one neighbour and exactly 2 other vertices. We add the 2 edges and complete the proof.