Prove that there is a group of 1010 people such that every person outside the group knows at least one person in the group. 
In a village there live $2021$ people, some of whom know each other. Everyone knows at least one other person. Prove that one can find a group of $1010$ people such that everyone outside this group knows at least one person in the group.

I tried small cases like $n=5,7...$ but they don’t work because you can have a case like that with $n=5$, (Denote person $1$ by $P_1$ )
$$P_1\to P_2, P_2\to P_3...P_5\to P_1$$
Where $P_1\to P_2$ Means person $1$ knows person $2$. Now, if you pick any group of $2$ people you will find at least one person outside the group that doesn’t know anyone in the group (You can choose the first person to be $P_1$ since everything is symmetric). So how are we supposed to solve this?
 A: This is equivalent to showing that the domination number of an $n$-vertex graph with no isolated vertices is at most $\lfloor n/2\rfloor$.
Take a minimum edge cover $C$ of the "knows" graph $G$ the greedy way – adding edges to a maximum matching $M$ to cover exposed vertices, possible since no vertex is isolated.
$C$ is a forest with $|M|$ connected components, since the added edges always connect one exposed vertex to one edge in $M$. But $C$ must also be a forest of stars, for if edges $ab$ and $cd$ are added adjacent to $bc\in M$, $abcd$ is an augmenting path, contradicting $M$'s maximality. The $|M|$ centres of $C$'s stars then dominate $G$, and here $|M|\le\lfloor2021/2\rfloor=1010$.
A: It seems your counterexample is correct. If the people are numbered 1 to 2021, and p knows p+1 except 2021 knows 1, then every person is known to exactly one other person. So if we pick any group G of at most 1010 people, then there are 1010 people knowing anyone in the group. So there are at most 2020 people who are either in G or know someone in G.
Assuming “X knows Y” implies “Y knows X”: Split the 2021 people into two groups A and B; initially A is empty and B is everyone. Then as long as some x in B knows nobody in A, move someone that x knows (x knows some y, which must be in B) from B to A. When eventually everyone in B knows someone in A, either A has 1010 or fewer members. Otherwise, everyone in A knows someone in B, but B has 1010 or fewer members.
