Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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$.

share|cite|improve this answer
It is a clear proof unrelated to graph theory. – Anthony Sep 8 '12 at 17:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.