The Erdős-Sós Conjecture for Geometric Graphs

Abstract

Let $f(n,k)$ be the minimum number of edges that must be removed from some complete geometric graph $G$ on $n$ points, so that there exists a tree on $k$ vertices that is no longer a planar subgraph of $G$. In this paper we show that $(1/2)\frac{n^2}{k-1}-\frac{n}{2}\le f(n,k)\le 2\frac{n(n-2)}{k-2}$. For the case when $k=n$, we show that $2\le f(n,n)\le 3$. For the case when $k=n$ and $G$ is a geometric graph on a set of points in convex position, we show that at least three edges must be removed.