We have a group of $n$ people, each of them knows at most three other persons in the group. How can one prove that the group can divided in two subgroups so that in each subgroup nobody knows more than one other person (in their subgroup!!!)? The relation is symmetric, so A knows B if and only if B knows A. Thanks in advance.
Combinatorial task about dividing a group of people into two parts.
combinatorics
Best Answer
It appears that a solution follows from the answer to this question:
https://mathoverflow.net/questions/247734/partition-of-a-graph-into-subgraphs-with-small-maximum-degree