Let be sets. For a subset of , let
Prove that for every integer , there exists a subset of such that and .
Solution
Let be a graph on vertices such that two vertices and are adjacent if and only if and . For a set of vertices of , let be the set of all vertices adjacent to every vertex in .
Suppose, on the contrary, that , and for all subsets with .
Solution 1
A set of vertices is called a clique if every pair of vertices are adjacent in . Let be a maximum clique of . It is trivial that .
(1) We claim that . If not, let be a set of vertices such that . Then and therefore there is a vertex adjacent to all vertices in . Then is a clique, contradictory to the assumption that is a maximum clique.
(2) No vertex has more than 1 neighbor in . Otherwise, if are adjacent to , then .
(3) Let and let be two vertices non-adjacent to . Since can not contain or , it must contain . Then is adjacent to at least vertices of , contradictory to (2) because .
Solution 2
Let be the degree of the vertex . By considering the number of pairs of a set of vertices and a vertex adjacent to all vertices of , we deduce
(1) If for all , then but because . Therefore there exists such that . We may assume .
(2) Let be the set of all neighbors of . Then . For a subset of with , since , there exists a unique vertex such that is adjacent to all vertices of .
If there are distinct subsets of each having vertices such that the corresponding vertices are identical, then is adjacent to all vertices in and so a subset of with vertices will have at least 2 common neighbors, contradictory to the assumption.
Therefore no two vertices corresponding to some subset of with vertices can be identical and so . But this is a contradiction because .
Solution 3
We use (1) of Proof 2 first to show that some vertex has degree at least .
We proceed by induction on .
If , then we use proof 1 to finish the proof.
If , then let be the neighbors of . For every subset of with vertices, we have and therefore the subgraph induced on has the property that every set of vertices has exactly one common neighbor. Since , such a graph can not exist by the induction hypothesis.