Bipartite Graph.

Question

Scientists have identified 20 traits for humans. Each person has 8 of these 20 traits before birth. In addition, human beings are unique and no one set of traits is the same. Show that a human being may acquire a new trait during his or her lifetime so that the human being remains unique.

Answer 1

Hint: For simplicity of argument, let's suppose that every possible set of $8$ traits corresponds to one of the humans so that there are the maximal number $\binom {20}{8}$ humans; if there aren't enough humans, then it is only easier to ensure that the humans remain unique after gaining a trait.

For each set $A$ of $8$ traits and $B$ of $9$ traits, connect $A$ to $B$ if and only if $A \subset B$. Each such set $A$ is connected to $20 - 8 = 12$ sets. A pair of distinct sets $A_1,A_2$ connect to a common set $B$ of $9$ traits if and only if $|A_1 \setminus A_2| = 1$, and in this case they both connect to $B = A_1 \cup A_2$.

---

Using this result: verify that the degree of each subset with size $8$ (each "human") has degree $20 - 8 = 12$, while each subset of size $9$ has degree $9$. The conclusion follows from the fact that $12 \geq 9$.