FKMO 2021 Problem 3

Let $P$ be a set of people. For two people $A$ and $B$ , if $A$ knows $B$ , $B$ also knows $A$ . Each person in $P$ knows $2$ or less people in the set. $S$ , a subset of $P$ with $k$ people, is called k-independent set of $P$ if any two people in $S$ don't know each other. $X_1, X_2, …, X_{4041}$ are 2021-independent sets of $P$ (not necessarily distinct). Show that there exists a 2021-independent set of $P$ , $\{v_1, v_2, …, v_{2021}\}$ , which satisfies the following condition:

[center] For some integer $1 \le i_1 < i_2 < \cdots < i_{2021} \leq 4041$ , $v_1 \in X_{i_1}, v_2 \in X_{i_2}, \ldots, v_{2021} \in X_{i_{2021}}$ [/center]

Let $G$ be a finite simple graph with maximum degree at most $2$ . Let $X_1, X_2, \ldots, X_{4041}$ be independent sets of size $2021$ (not necessarily distinct). Prove that there exists another independent set $\{v_1, v_2, \ldots, v_{2021}\}$ of size $2021$ and indices $1 \le t_1 < t_2 < \cdots < t_{2021} \le 4041$ such that $v_i \in X_{t_i}$ for all $i$ .