A geometric graph is a set of points in the plane (vertices) and a set of line segments between certain pairs of points (edges). A geometric graph is simple if the intersection of two edges is empty or a vertex of both. A geometric graph is convex if the vertices are in convex position. A geometric caterpillar is a geometric tree that looks like this.

**Theorem** (Micha Asher Perles, mid 80s): Let *T* be a caterpillar with *k* edges. Every convex geometric graph with* [n(k-1)/2]+1* edges contains a simple copy of *T*. As a matter of fact, *T* can be embedded in G is an orientation preserving manner.

**Proof: **Let *G* be a convex geometric graph with *n* vertices and *e* edges. For every edge of *G* we will consider two half edges, where a half edge is a small subinterval of the edge containing one of its vertices. Thus *G* has *2e* half edges.

Let *T* be a caterpillar with *k* edges. Suppose that the left most non-leave,* b*, of *T* has *m+1* neighbors and let *S* be the geometric caterpillar obtained by removing from *S* the m left most neighbors of a and the edges containing them. *S* has *k-m* edges. Let *w* denote the left most half edge of* T*.

An half edge *u* of *G* is **good** (for *T*) if we can embed *T* in an orientation preserving manner so that *w* is mapped to *u*. Otherwise, u is **bad**.

the following is stronger than the Theorem.

**Claim:** There are at most *(k-1)n* bad half edges.

Proof by induction on *T*. For every vertex of *G* call its m left most half edges **nasty**. By induction G has at most (k-m)n bad (for S) half edges. Altogether there are at most *(k-1m)n+mn=(k-1)m* half edges which are either bad for S or nasty. We map every half edge y coming from a vertex x which is neither nasty nor bad for S to another half edge z as follows. First consider the half edge which is the* (m+1)*th to its left from *x*. (There is such a half edge because y was not nasty.) The other half edge on the same edge. This half edge is good for *T* and therefore there are at most* (k-1)n* bad half edges for *T*. **Sababa!**

Remarks: See this post for a proof about geometric graphs by lice. The Erdos-Sos conjecture (whose solution for was achieved by Ajtai, Komlos and Szemeredi) asserts that a graph with *n* vertices and more than *[(k-1)n/2]* edges contains every tree with *k* edges. (See, here and here). The case where is a path was proved by Erdos and Gallai.

Interesting problem. I’m not sure I understand the end of the proof of the claim, though.

You map the (m+1)th left half-edge coming from x to the other half-edge on the same edge? and you do the same with the (m+2)th left half-edge, (m+3)th… etc.? and all these half-edges are good for T? is this the mapping? Also, I think that in the second line of the proof of the claim it should be (k-m-1) instead of (k-m), and the r.h.s. of the equation in the beginning of the following line should be (k-1)n.