# Perles’s geometric caterpillar argument These notes use the same notation and construction as the presentation. The source is [Gil Kalai’s account of Micha Perles’s proof, August 29, 2017](https://gilkalai.wordpress.com/2017/08/29/micha-perles-geometric-proof-of-the-erdos-sos-conjecture-for-caterpillars/). The algebra is corrected below. The source’s implicit geometric convention is stated explicitly so that the gap argument and the injection can be checked independently. ## 1. Definitions and the prescribed order A **geometric graph** has distinct points as vertices and straight segments as edges. Throughout, graphs are finite and simple. A graph is **convex** when its vertices are in strictly convex position. In particular, no three vertices are collinear. Its boundary supplies an oriented cyclic order. A geometric copy is **simple** if two chosen edges intersect only at a common endpoint. Extra edges in the host graph do not count as part of the copy. The copy need not be induced. An **orientation-preserving** embedding is an injective map of target vertices that preserves adjacency and the prescribed cyclic vertex order, without reflection. In convex position, the cyclic vertex order determines the local incident-edge orders. A **caterpillar** is a tree whose non-leaf vertices induce a path, allowing a single vertex or an empty path in the small cases. That path is the **spine**. Its size parameter is its number of edges, not its number of vertices. The geometric caterpillar in the source is given a zigzag drawing with terminal leaf bundles on alternating local sides of the spine. To make the geometric information exact, use the following recursive boundary-order convention for its convex realization: 1. A one-edge target can have either endpoint as its root tail. Fix either boundary sign; there is no third vertex to constrain it. 2. Suppose the smaller rooted caterpillar S has root (b,c), where b is a leaf, and b,c are consecutive in its cyclic vertex order. 3. In the direction in which c is the first S vertex after b, insert a terminal bundle a₁,…,aₘ into the empty arc from b to c. Add baᵢ for every i, keeping the rest of S. The new root is (a₁,b). Thus, in the direction used for this extension, the vertex order is ``` S: b, c, [the remaining vertices of S] T: b, a₁, …, aₘ, c, [the remaining vertices of S]. ``` The root endpoints of T are again consecutive, but their orientation relative to this cyclic direction is reversed. Consequently the direction used in the next recursive stage reverses. This is the precise meaning of alternating **local** sides. It is not a globally fixed “above” or “below.” This convention spells out the source’s prescribed zigzag geometric caterpillar. An arbitrary convex ordering of the same abstract tree is not interchangeable with it. In particular, “b is a leaf of S” alone would not imply that bc is a convex-hull edge. The prescribed root-boundary property is needed, and is preserved by the recursive convention. A **half-edge** is an endpoint incidence of an edge. Write (p,q) for the half-edge of pq at p. It can be drawn as a short segment near p. The reversal map is R(p,q) = (q,p). The set H(G) of host half-edges has cardinality 2e. In the prescribed T, let w = (a₁,b) be the leftmost half-edge in the zigzag drawing. A host half-edge u is **good for T** if a simple, orientation-preserving embedding maps w to u. It is **bad for T** otherwise. Goodness requires an entire copy of T. Write bad(T) and good(T) for these sets. For S, the prescribed root is wS = (b,c). ## 2. The theorem Let T be a prescribed geometric caterpillar with k ≥ 1 edges, with the order just specified. Every convex geometric graph G on n vertices with \[ e \ge \left\lfloor\frac{n(k-1)}2\right\rfloor+1 \] contains a simple, orientation-preserving copy of T. Since e is an integer, the hypothesis is equivalent to \[ 2e>(k-1)n. \] The host may have crossings. Only the edges chosen for T must form a simple copy. Every abstract caterpillar admits the prescribed geometric realization, so this geometric theorem also gives the abstract caterpillar case of the Erdős–Sós assertion. ## 3. Stronger claim and base case For every convex host G, without any density hypothesis, \[ \#\operatorname{bad}(T)\le(k-1)n. \] We prove this by induction on k, for the prescribed rooted targets with either boundary sign. For k = 1, every existing half-edge supports the rooted one-edge target. Thus there are zero bad half-edges, as required by (k−1)n = 0. If H(G) is empty, the same statement is vacuous. ## 4. The smaller target For k > 1, let b be the first non-leaf spine vertex. It has m leaf neighbors a₁,…,aₘ and one continuation neighbor c, so degT(b) = m+1. Here m ≥ 1. In the star case, designate the last leaf in the prescribed order as c and retain the edge bc; this produces the one-edge target. Delete a₁,…,aₘ and their incident edges. The remaining target S has exactly k−m edges. The vertices b,c and edge bc remain; b now has degree one. The prescribed root of S is (b,c), and its boundary sign is the opposite of the root sign of T. By the recursive convention, bc is an edge of the convex hull of S’s vertices in every orientation-preserving convex copy. By induction, \[ \#\operatorname{bad}(S)\le(k-m-1)n. \] Notice the subtraction of **one after** substituting the smaller edge count k−m. ## 5. Local order and nasty roots Fix the direction for this stage as follows: in S’s prescribed root order, c is the first vertex after b in that direction. This is either clockwise or counterclockwise. Use that same direction at every host vertex; it is independent of the embedding witness. At each host vertex x, cut the cyclic host-vertex order at x, then read its neighbors in this direction. Write them as v₁,…,v_d, where d = degG(x). This produces a linear order with a first position; an uncut circular order would not suffice. Call the first min(m,d) half-edges at x **nasty**. Let Nₘ be the set of all such half-edges. Then \[ |N_m|=\sum_{x\in V(G)}\min(m,\deg_G(x))\le mn. \] Non-nasty means precisely that y = (x,vⱼ) has j > m. Its m preceding positions j−m,…,j−1 therefore exist. Nasty roots may also be bad for S; no disjointness is assumed. ## 6. Gap-extension lemma **Lemma.** Suppose y = (x,vⱼ) is good for S in the stage’s prescribed order, and j > m. A witness embedding of S extends to a simple, orientation-preserving embedding of T with \[ b\mapsto x,\qquad c\mapsto v_j,\qquad a_i\mapsto v_{j-m+i-1}\quad(1\le i\le m). \] **Unused interval.** In the witness, b,c are consecutive in the S boundary order, with c first after b in the chosen direction. Every other embedded vertex follows c in the linear order cut at x. Therefore the open host-boundary arc from x to vⱼ contains no vertex of the witness. All m selected preceding neighbor endpoints lie in that arc, are distinct, and are absent from S. The arc is empty **of embedded S vertices**, not empty of host vertices. Its available host vertices are exactly what makes restoration possible. We do not move S or relocate any host vertex. Peeling exposes the target gap; the witness places that gap on the host boundary. The shift selects the first new leaf/root within it. **Boundary and angle.** The edge xvⱼ = bc joins consecutive vertices of the embedded S, so it is a boundary edge of conv(S). The unused arc lies on the exterior side of its supporting line. The cap bounded by that arc and bc supplies the available local sector at b. Since degS(b) = 1, there is no second incident S edge at b “immediately before bc.” Such informal wedge language must be understood using the supporting hull edge and the empty arc. In the one-edge S case, the hull is a segment and the chosen boundary sign selects the available side. This is the geometric interpretation used by the deck. **Existence of edges.** Each vᵣ in the list is a neighbor of x in G. Thus every required new edge x v_(j−m+i−1) is already a host edge. No edges are invented. **Noncrossing.** For four distinct vertices of a strictly convex polygon, two straight chords cross internally if and only if their endpoints alternate on the boundary: a chord separates the polygon into two convex parts, and the other chord crosses it exactly when its endpoints are on opposite open boundary arcs. This applies also when other polygon vertices occur between the four endpoints. All new edges share x, so no two have an interior crossing; no three vertices are collinear. For a new edge xaᵢ and an old edge pq disjoint from it, both p and q lie outside the empty arc from x to c. They cannot alternate with x,aᵢ. Hence the new edge cannot cross pq. An old edge incident with x only meets it at x. Old edges do not cross each other by the simplicity of the witness. **Orientation.** The old vertices retain their order, and the new vertices occur between b and c in the order a₁,…,aₘ. This is exactly T’s prescribed recursive cyclic order. Thus the embedding preserves orientation, including the local edge order of each fan. The extension maps w = (a₁,b) to z = (v_(j−m),x). Therefore z is good for T. ∎ ## 7. Shift, reversal, and injectivity On non-nasty half-edges define \[ Q_m(x,v_j)=(x,v_{j-m}),\qquad F=R\circ Q_m,\qquad F(x,v_j)=(v_{j-m},x). \] This is a shift by m positions, then a reversal across the **same selected edge**. The selected edge is itself the first new leaf edge. There are m−1 other positions strictly between it and y, giving m new leaf edges in total. The edge underlying y is retained as bc. Qₘ is injective. Its first coordinate retains x. At a fixed x, different indices j have different indices j−m, and distinct neighbors determine distinct half-edges. Reversal R is an involution on H(G), so it is bijective. Hence F is injective. An explicit inverse on the image is: reverse z to recover (x,vᵣ), recover r in x’s fixed local list, and return (x,v_(r+m)). This also proves injectivity for roots with different tails, including roots whose selected undirected edge happens to be the same. The map does not depend on a choice of S witness. The gap lemma applies to any suitable witness, but every eligible y has a single deterministically defined image z. ## 8. Corrected counting calculation Following the supplied draft and the presentation, name the excluded union A = bad(S) ∪ Nₘ. Let \[ D=H(G)\setminus\bigl(\operatorname{bad}(S)\cup N_m\bigr). \] The gap lemma and injectivity give F(D) ⊆ good(T) and |F(D)| = |D|. Consequently, \[ \begin{aligned} \#\operatorname{bad}(T) &=2e-\#\operatorname{good}(T)\\ &\le 2e-|D|\\ &=|\operatorname{bad}(S)\cup N_m|\\ &\le\#\operatorname{bad}(S)+|N_m|\\ &\le(k-m-1)n+mn\\ &=(k-1)n. \end{aligned} \] This is a cardinality argument through an injection. It does not assert the generally unjustified set inclusion bad(T) ⊆ bad(S) ∪ Nₘ. Induction continues until the one-edge case. For the running example, the edge counts are 12, 9, 6, 3, 1, with removed bundle sizes 3, 3, 3, 2. The host G and its n vertices are fixed throughout. ## 9. Conclude the theorem If 2e > (k−1)n, the 2e half-edges cannot all be bad. A good half-edge supports an entire simple, orientation-preserving T by definition. This proves the theorem. Strict inequality is essential to this final inference. ## 10. Notation | Symbol | Meaning | |---|---| | G, n, e | Convex host graph; its numbers of vertices and edges | | T, k | Prescribed geometric caterpillar; its number of edges | | H(G) | All 2e host half-edges | | (p,q), R | Half-edge of pq at p; reversal R(p,q) = (q,p) | | b | First non-leaf spine vertex of T | | a₁,…,aₘ | Terminal leaf bundle removed at b | | c | The one neighbor retained as the continuation from b | | m | Number of removed leaf edges; degT(b) = m+1 | | S | Smaller rooted target with k−m edges | | w, wS | Target roots (a₁,b) and (b,c) | | u | An arbitrary candidate host half-edge | | x | Host image of b | | v₁,…,v_d | Neighbors of x in the stage’s fixed linear order | | y = (x,vⱼ) | A non-nasty root good for S, with j > m | | Nₘ | Nasty roots, at most m at each host vertex | | Qₘ | Local index shift j ↦ j−m | | z = F(y) | Reversed shifted root (v_(j−m),x), good for T | | A | The excluded roots bad(S) ∪ Nₘ; “nasty” in the slides means Nₘ | | D | Roots simultaneously non-nasty and good for S, namely H(G) ∖ A | | conv(S) | Convex hull of the vertices of the embedded S | ## 11. Source corrections and interpretations The source’s removal sentence accidentally names S as the graph from which S is obtained and refers to a where b is required. The construction removes the m leaf neighbors a₁,…,aₘ of **b from T**, yielding S. The induction coefficient must be **k−m−1**, not k−m. The garbled subsequent calculation must read **(k−m−1)n + mn = (k−1)n**, with n as the final factor. The source’s ordinal description of the shift is ambiguous. We count y inclusively when referring to the (m+1)th position toward the chosen side; the exact index map is j ↦ j−m. Counting m+1 predecessors strictly would require an extra edge and would not follow from non-nastiness. The boundary-root convention, its alternating direction, the gap-extension lemma, and injectivity are expanded here because the brief source leaves them implicit. In particular, the gap is outside conv(S), the selected edge counts as one of the m leaf edges, and the “wedge” does not require a second S edge at its degree-one root. None of these steps is justified merely by saying that a target is a tree.