# How many non-intersect line segments are possible for given points proof?

I'm looking for a proof for this question/near-answer

Take any set of $K$ points on the plane where no $3$ are colinear. How many line segments can be created, regardless of order, before any intersect?

Create a convex polygon using the points as vertices, such that it encompasses all other points, it will be an $N$-gon. Then with the remaining interior points do the same, until you have no points, the last polygon(sometimes a line or point) will have $V$ vertices.

The number will be based on $K,N,\&V$ and will roughly be $3N-K$

Your tag choice was right. :-) Any maximal configuration of non-intersecting segments between given points can be considered as a plane graph $G$, whose outer face is the $N$-gon. Count the number $x$ of pairs $(e,f)$ where $e$ is an edge incident to a face $f$ of the graph $G$. Since each but outer face of $G$ has at least $3$ egdes and the outer face of $G$ has $N$ edges, $x\ge 3(f(G)-1)+N$, where $f(G)$ denotes the number of faces of $G$. On the other hand, each edge of the graph $G$ is incident to at most two faces of $G$, so $x\le 2e(G)$, where $e(G)$ denotes the number of edges of $G$. Thus $2e(G)\ge 3f(G)+N-3$. By Euler’s formula, $f(G)=e(G)-K+2$. It follows $e(G)\le 3K-N-3$. This upper bound is achieved by any almost-triangulation $G$, that is when $G$ has all but the outer faces triangles. We can construct one of them recursively as follows. Pick any vertex $v$ of the $N$-gon, construct an almost triangulation $G’$ on the remaining points, an then connect by segments the vertex $v$ with the vertices of the outer face of $G’$ which are visible from $v$.