What is the minimum number of edges in this special graph? Assume that graph $G$ has $2n$ vertices and special property: If we select any $n$ vertices, among them there should be a vertex $v$ connected with rest $n-1$ vertices. What is the minimum number of edges in this graph?
My attemps are the following:


*

*Select any $n$ vertices. There must be $n-1$ edges from a vertex $v$. Remove the vertex $v$ from the graph and repeat. So there are at least $(n-1)(n+1)=n^2-1$ vertices in a graph. It is clear that an edge is counted only once.

*There are $2n \choose n$ subsets of $n$ vertices with at least $n-1$ edge in a subset. Every edge is counted at most $2n-2 \choose n-2$ times, so there are at least $4n-2$ edges. This is even worse than first attempt.


My experiments with small graphs shows that lower bound must be at least 2 times greater, if not more. 
It is clear that both my approaches are dumb, something more elegant must be used. 
Can you help with it? Thanks a lot for your time and ideas.
 A: Consider the graph $\overline G$, the graph with the same vertex set as $G$ and edge set defined by: $u$ and $v$ are connected in $\overline G$ if and only if they are not adjacent in $G$. Then the property
$$\text{For any $n$ vertices $v_1,\ldots,v_n$ in $G$, one vertex $v_1$ is adjacent to all of $v_2,\ldots,v_n$}\tag 1$$
is equivalent to
$$\text{For any $n$ vertices $v_1,\ldots,v_n$ in $\overline G$, one vertex $v_1$ is not adjacent to any of $v_2,\ldots,v_n$.}\tag 2$$
Claim 1. When $n$ is even, $(2)$ holds if and only if there are at least $n+1$ vertices of degree $0$.
$(\Rightarrow)$ Suppose, for a contradiction that there are at most $n$ vertices of degree $0$, then there are at least $n$ vertices of degree $1$ or more. Consider the subgraph $H$ of $\overline G$ induced by the $k\ge n$ vertices of positive degree. If $k=n$ then we are done since property $(2)$ cannot hold for these $n$ vertices. So suppose $k>n$; now I remove vertices from $H$ as described below, at each stage we do not have any vertices of $H$ with degree $0$ in the induced subgraph. If there is a connected component of $H$ of odd size, remove a vertex of degree $1$, if it can be found; otherwise remove an arbitrary vertex—if removing a vertex $u_1$ would have $\mathrm{deg}\, u_2=0$, then $u_2$ had degree $1$ before removal. If the smallest connected component of $H$ has size $2$ and all connected components have even size, then remove the smallest one (since $n$ is even, $k\ge n+2$ if there are no odd components). If the smallest connected component of $H$ is even and has size larger than $2$, remove a vertex of degree $1$, if it can be found; otherwise remove an arbitrary vertex—if removing a vertex $u_1$ would have $\mathrm{deg}\, u_2=0$, then $u_2$ had degree $1$ before removal. By repeating this, we can reach a point where $H$ has size $n$ and no isolated vertex, i.e. $(2)$ cannot be satisfied.
$(\Leftarrow)$ Any choice of $n$ vertices from $\overline G$ must contain one of the vertices of degree $0$, of which there are $n+1$ (pigeonhole principle).
Claim 2. When $n$ is odd, $(2)$ holds if and only if there are at least $n+1$ vertices of degree $0$, or no vertex of degree $2$ or more. 
$(\Rightarrow)$ Reason as before, by contradiction, to get the subgraph $H$ of $\overline G$ induced by the $k\ge n$ vertices of positive degree. If $k=n$ we are done, so suppose $k>n$. Consider the connected component $C$ of $H$ which contains the vertex $v$ of degree at least $2$. If $C$ has even size $|C|\ge 4$, then remove a vertex of degree $1$, if it can be found; otherwise remove an arbitrary vertex. Hence, we may assume that $C$ has odd size, say $|C|=m\ge 3$, and no isolated vertices. Call the remainder $H^\prime=\overline G-C$ minus the aforementioned removed vertex—if applicable. In the same way as before, trim $H^\prime$ down until it has size $k^\prime=n-m$, at each stage prioritising odd sized connected components, then components of size $2$, then larger even sized components. (Note that if there are no odd components of $H^\prime$, the smallest component is of size $2$, and $|H^\prime|>n-m$, then since $|H^\prime|$ and $n-m$ are both even, the smallest component can be safely removed while preserving the inequality $|H^\prime|\ge n-m$.) After this is done, $H^\prime+C$ has size $n$ and no isolated vertices, so property $(2)$ cannot hold.
$(\Leftarrow)$ If $\overline G$ has no vertex of degree $2$ or more, then it is a collection of $K_2$s and $K_1$s. Since $n$ is odd, any choice of $n$ vertices will have a vertex that is in its own connected component. If there is a vertex of degree $2$ or more then, as in claim one, any choice of $n$ vertices from $\overline G$ must contain one of the vertices of degree $0$
Bounds for the properties. A minimum bound $M$ on the number of edges to satisfy $(1)$ is an upper bound on the number of edges that can satisfy $(2)$.
When $n$ is even, at least $n+1$ vertices need to be degree $0$; including all possible edges in the remaining $n-1$ vertices gives $\tfrac 12(n-1)(n-2)$ edges. When $n$ is odd, we can do better when $n=1$, $n=3$ or $n=5$: a graph with no vertex of degree $2$ or more is (at best) a collection of $K_2$s, and has $n$ edges. Then $M$ is the difference between $\tfrac 12(2n)(2n-1)$ and these numbers. Hence
$$M=\begin{cases}
2n^2-2n&\text{$n=1$, $n=3$ or $n=5$},\\
\tfrac 12(3n^2+n-2)&\text{otherwise}.
\end{cases}$$

Remark. It is also possible to work directly with property $(1)$. Notice that (excluding the special cases $n=1$, $3$, $5$) graphs that satisfy the minimum bound are split graphs of $2n$ vertices with clique of size $n+1$ and independent set of size $n-1$. The number of edges in such graphs is $$(2n-1)+(2n-2)+\cdots+(n-1).$$
The crux here being that any choice of $n$ vertices will intersect with the clique, hence contains a vertex adjacent to the other $n-1$ vertices. We cannot improve on this bound, because removing an edge $u_1u_2$ from the clique will produce a set $\{u_1,u_2,v_3,\ldots,v_n\}$ (where $v_3,\ldots,v_n$ are from the independent set) which does not satisfy $(1)$. Since $v_3,\ldots,v_n$ form an independent set, they cannot be the 'special' vertex which is adjacent to the others. Nor can $u_1$ and $u_2$ have the property—they are not adjacent to each other!
It would take a bit of work to show that this is an optimal formulation for all $n$ except $1$ ,$3$ and $5$ (I am not sure how to do that).
A: My approach would be to consider how many edges you can remove from the complete graph on $2n$ vertices ($K_{2n}$) and still meet the criteria. For $n=2$ any two vertices selected fom $K_4$ must induce an edge, so the answer is none (zero edges can be removed). 
For $n=3$, it seems you can remove the 3 mutually non-adjacent edges of $K_6$ and meet the criteria. Then any 3 vertices you select will induce either $K_3$ or $P_3$, both of which have a vertex of degree $n-1=2$. 
$n=4$ is interesting. It seems you can remove at most 3 mutually adjacent edges of $K_8$. The removal of any two non-adjacent edges, say $st$ and $uv$ would allow you to select $\{s,t,u,v\}$  which induces $C_4$ where every vertex has degree $n-2=2$. 
I haven't worked it through, but I think this can be generalized. It seems like you'll have to consider two cases for odd and even $n$. 
