Find such minimal $n$ that everybody from $100-n$ people have a friend in group of n people.

Question

• There's 100 people in the company.

• For every group with 10 members there's at least one triplet of pairwise friends
  (on the graph it would look like a triangle).

Find such minimal $n$ that the following statement is true: There's group of n people such that everybody from the remained 100-n people have a friend in that group.

My attempt: Firstly we should split our task to subtasks. Knowing minimal number of edges in graph with 100 vertices that satisfy our condition is the main problem here. If we manage to find such number of edges it wouldn't be a problem to find $n$. Firstly I thought about Turán graph (https://en.wikipedia.org/wiki/Tur%C3%A1n_graph#Tur.C3.A1n.27s_theorem) with 10 groups of 10 vertices but inside each group we should also add some edges to satisfy condition. But I think that graph has too many edges to be minimal. Ok, let's assume that number of minimal edges is known. I suppose that every vertex has the same degree because of independence of forming group order. Here we could choose numbers from $n=1$ so that every another added vertex isn't connected with previously connected vertices. We will stop when number of connections in our group will reach or exceed number of people in group 100-n.

PS: Probable answer is $n=8$

Answer 1

We first prove $n>7$. Let $n\in [7]$, and let $G$ be comprised of $K_{100-n}$ and an independent set $I$ of size $n$. Any subset $S$ of $V(G)$ with $|S|=n$ either contains all of $I$, in which case there are no edges between $S$ and $V(G)\backslash S$, or does not contain a vertex $i\in I$, in which case $i$ does not have an edge to $S$. Thus $G$ does not contain a set of $n$ vertices such that the other $100-n$ vertices all have a neighbour in said set.

We now show that $n=8$ works. Since every set of $10$ vertices contains a triangle, every set of $9$ vertices contains an edge. Hence, the independence number $\alpha(G)$ (the size of a largest independent set of $G$), is at most $8$. Let $I$ be an inclusionwise maximal independent set, so $|I|\leq 8$. By definition, any $v\in V(G)\backslash I$ has a neighbour in $I$. If $|I|=8$, we are done. If $|I|<8$, add vertices to $I$ until the new set $I'$ obtained has size $8$. All vertices in $V(G)\backslash I'$ have a neighbour in $I'$ since they have a neighbour in $I$. Thus, the answer is $n=8$.