Consider a set $P$ of $n$ points in the plane. Using $n-1+k$ line segments, $k\geq 0$, these points can be connected (i.e., the graph in which the points are the vertices and the line segments the edges is a connected graph). For each $k$, there is a (possibly nonunique) way to choose the $n-1+k$ connecting line segments so as to minimize their total length. Call a set of $n-1+k$ length-minimizing connecting line segments $G_k$, and call the set of all such sets $g_k$. That is, $g_k$ is the set of all solutions to the problem of connecting the points in $P$ using $n-1+k$ line segments with the shortest total length.
Is it true that any element of $g_{k+1}$ can be obtained by adding one line segment to some element of $g_k$? Or are there "nontrivial" solutions, elements of $g_{k+1}$ that cannot be constructed from any element of $g_k$ without removing some line segments?
My intuition is that there are no "nontrivial" solutions, but I haven't been able to prove this.
Yes it is true.
Take any minimal tree of $G_{k+1}$, and remove any edge that is not in this tree. You will get something in $g_k$.