Maximum number of edges one can add to a tree without making it non-planar

I actually have a question regarding the accepted answer to this question by the OP themself:

How many edges can you add to a tree with $n$ vertices so it stays planar?

The answer employs induction on the assumption that one can add $3(n-1)-6-(n-2)=2(n-1)-5$ edges to a tree with $n-1$ vertices so that the newly obtained graph is again planar.

To prove the statement for a tree with $n$ vertices, we need to remove one of the at least two leaves. The OP writes we then add $2(n-1)-5=2n-7$ edges and all the faces inside the graph are incident with exactly $3$ vertices. If they were incident with $4$ vertices, we could add another edge to connect two non-neighbouring vertices, which would be a contradiction (I believe it is due to the number of added edges exceeding the maximum possible for a graph to remain planar). Now, the last part, which I'm not quite sure about, we should add the previously removed leaf, which would now lie on a face incident with its neighbour and $2$ other vertices. My question is:

Do we put that leaf on any of the faces, each of whom is incident with some $3$ vertices of the graph, or do we expect that particular leaf to be on the right position from the beginning, that is, we know it isn't somewhere outside in the plane where the graph is embedded?

And if that leaf is inside a triangle with its neighbour as one vertex, does it matter which of the vertices we're going to connect with the leaf?

It's important to distinguish a graph (even a planar one) from a plane embedding of the graph. The graph is just an abstract adjacency relationship between arbitrary objects called vertices. It's the plane embedding that puts the vertices and edges down in the plane.

In the induction step, we assume that we have an $n$-vertex tree $T$: a graph. It has a leaf (call it $v$), and so $T-v$ is an $(n-1)$-vertex tree.

By the induction hypothesis, we can add $2n-7$ edges to $T-v$ to get a planar graph $G$; now take a plane embedding of $G$. In this plane embedding, the vertex $v$ does not have a location - after all, $v$ is not a vertex of $G$ at all! However, $v$ had a single neighbor (call it $w$) in $T$, so $w$ is a vertex of $T-v$, and therefore $w$ is a vertex in $G$.

The vertex $w$ has a location in the plane embedding. Now we can modify the plane embedding to get a bigger plane embedding of a graph $G^+$ that contains $G$, an additional vertex $v$, the edge $vw$, and $2$ more edges. To do this:

• Place $v$ inside any face (call it $F$) whose boundary contains $w$.
• Add edges from $v$ to $w$ and to two other vertices on the boundary of $F$; in the plane embedding, these edges can be drawn inside $F$ without crossing.
• Note: in principle, it can be shown that there's no choice here - $F$ must be a triangle, and so we add edges from $v$ to every vertex on the boundary of $F$. But for the proof, it's enough to know that $F$ must have at least $3$ vertices on its boundary, so we can add at least the edges above.

The resulting graph $G^+$ contains $T$ as a subgraph: it contains $T-v$ as a subgraph, and also the edge $vw$, which is also what we need to get $T$. Also, it has $3$ more edges than $G$, so we can count and conclude that it has $2n-5$ edges more than $T$.