# A Graph Theory Problem

Define $P(S)$ as $$\exists a, b \in S (a - b \in S).$$

Prove that for any subset $S$ of $A = \{1, 2, 3, 4, 5\}$, $P(S)$ or $P(A - S)$ holds.

Please prove it using some graph theory.

-

Assume $\neg P(S)$ and $\neg P(A-S)$. Since $4-2=2$, at most one of 4 and 2 is in $S$ and at most one of them is in $A-S$, hence exactly one is in $S$ and onw is not. By the same argument, exactly one of 1 and 2 is in $S$. By symmetry in $S$ vs. $A-S$, we may assume that $1\in S$, hence $2\notin S$, $4\in S$. Then we conclude $3=4-1\notin S$, $5=4+1\notin S$. But then $2=5-3$ holds in $A-S$.