MathDB
Two element subsets of a graph

Source: 2019 China Second Round P4

September 8, 2019
combinatoricsgraph theory

Problem Statement

Let VV be a set of 20192019 points in space where any of the four points are not on the same plane, and EE be the set of edges connected between them. Find the smallest positive integer nn satisfying the following condition: if EE has at least nn elements, then there exists 908908 two-element subsets of EE such that [*]The two edges in each subset share a common vertice, [*]Any of the two subsets do not intersect.