This paper by Erdős and Stone presents a theorem on the structure of linear graphs. The theorem states that for any given ε > 0 and integer r ≥ 2, there exists a number n₀(ε, r) such that for every n > n₀, any linear graph with n vertices and fewer than (1/2(r-1) - ε)n² edges contains r mutually exclusive groups of k vertices each, where k ≥ (l_{r-1}(n))^{1/2}, such that no two vertices in different groups are joined. The proof is by induction over r, and uses a combinatorial lemma. The lemma shows that given N subsets of a set E of n elements, each of size at least p ≥ k, there exist at least NC_{p,k}/C_{n,k} of the subsets whose intersection has at least k elements. Corollaries of this lemma are used to prove the theorem. The theorem is restated in terms of the complementary graph, and the case r=2 is considered separately. The proof for r ≥ 3 uses the theorem for r-1 and leads to a contradiction if c > 0, where c is the greatest lower bound of admissible ε. The paper also mentions other theorems and conjectures, including Rademacher's theorem on the number of triangles in a graph. The paper concludes with a remark that the estimate for k can be improved, and that the number of edges required by the theorem is substantially best possible.This paper by Erdős and Stone presents a theorem on the structure of linear graphs. The theorem states that for any given ε > 0 and integer r ≥ 2, there exists a number n₀(ε, r) such that for every n > n₀, any linear graph with n vertices and fewer than (1/2(r-1) - ε)n² edges contains r mutually exclusive groups of k vertices each, where k ≥ (l_{r-1}(n))^{1/2}, such that no two vertices in different groups are joined. The proof is by induction over r, and uses a combinatorial lemma. The lemma shows that given N subsets of a set E of n elements, each of size at least p ≥ k, there exist at least NC_{p,k}/C_{n,k} of the subsets whose intersection has at least k elements. Corollaries of this lemma are used to prove the theorem. The theorem is restated in terms of the complementary graph, and the case r=2 is considered separately. The proof for r ≥ 3 uses the theorem for r-1 and leads to a contradiction if c > 0, where c is the greatest lower bound of admissible ε. The paper also mentions other theorems and conjectures, including Rademacher's theorem on the number of triangles in a graph. The paper concludes with a remark that the estimate for k can be improved, and that the number of edges required by the theorem is substantially best possible.