Delightful set of vertices is exactly a maximal independent set which it's complement is the minimal vertex cover. By Konig's theorem then the size of the minimal vertex cover is the same as the maximal matching. And the maximal matching would be, when the graph is bipartite with two sets with the same size $=5000$, so the maximal matching is $5000$. That means the size of the maximal independent set is $10 000 - 5000 = 5000$.

TheMathBob wrote: Delightful set of vertices is exactly a maximal independent set which it's complement is the minimal vertex cover. By Konig's theorem then the size of the minimal vertex cover is the same as the maximal matching. And the maximal matching would be, when the graph is bipartite with two sets with the same size $=5000$, so the maximal matching is $5000$. That means the size of the maximal independent set is $10 000 - 5000 = 5000$. There is a counterexample showing that $m\ge10000-2\cdot100+2$. The counterexample is constructed as follows: First let there be a clique of a hundred vertices $v_1, v_2, \dots v_{100}$. Now connect each one of these vertices with exactly $99$ other vertices so that no two $v_i$'s share any one of the $99$ vertices.

So here is a solution. Answer: $m=9802$. General problem: Let $n^2$ be the number of vertices. Then $m=n^2-2n+2$. Example: As in my above post. Achievability: Assume that for a graph $G$ the best possible $m$ is $n^2-k$ with $k\le 2n-3$. It's easy to see that any anticlique of size $<n^2-k$ is contained in an anticlique of size $=n^2-k$. Now let's look at an example where $m=n^2-k$ is achieved(I put a picture for better visualization). Let $A$ be the anticlique of size $=n^2-k$ and $B$ be the set of the rest of the vertices of size $=k$. Let $v$ be a vertex in $B$ with the maximal amount $t$ of neighbors in $A$. Let this set of neighbors be $T$ of size $=t$. Then $\{v\}\cup(A\backslash T)$ is an anticlique of size $=n^2-k-t+1$. Then there is an anticlique $C$ of size $=n^2-k$ containing it. It's obvious that $T\cap C=\emptyset$, thus $|C\cap B|= t$. Now let $D=B\backslash C$ of size $=k-t$. Now let's look at how many edges are between $A\cap C$ and $D$. On one hand, every edge out of $A\cap C$ has to end in $D$. So this amount is $\ge n^2-k-t$. On the other hand, every vertex of $D$ has at most $t$ neighbors in $A$. Thus this amount is $\le (k-t)\cdot t$. We get: $kt-t^2\ge n^2-k-t \newline$ $0\ge t^2-(k+1)t+n^2-k=(t-\frac{k+1}{2})^2+n^2-((\frac{k+1}{2})^2+k)\ge n^2-(2n-3+(n-1)^2)=2>0$ contradiction!!!

Attachments: