Prove that $G$ contains a vertex $z$ with $d(z)=2k$ Let $G$ be a graph of order $2k+1, k\geq1$. Suppose that for any subset $A$ of $k$ vertices, there is a vertex $v \notin A$ such that $v$ is adjacent to each vertex in $A$. Prove that $G$ contains a vertex $z$ with $\deg(z)=2k$.
Intuitively I thought of trying to prove this by contradiction - suppose all the vertices in $G$ have degree at most $2k-1$, and consider the vertex with maximum degree. I tried to construct another vertex with a greater degree to arrive at a contradiction, but was at a loss on how to do it. Another approach I considered (by using contradiction) was applying the Handshaking Lemma to claim that $e(G)\leq2k^2-\dfrac{1}{2}$, but I have no clue how to use the given condition in the problem to bound the number of edges in $G$.
Any hints towards solving the problem (not a full answer) will be much appreciated.
 A: HINT: Work with the complement $G^c$ of $G$: In $G^c$ for every subset $A$ of $k$ vertices, there is at least one vertex $v \not \in A$  in $A^c$ that is adjacent to no vertices in $A$. Show that $G^c$ must have at least one vertex that has degree $0$ s follows:

First, note the following claim:


 >Claim 1: Let $C$ be any connected graph with at least $2$ vertices. Then there is a subset $A_C$ of half the vertices of $C$ [or if $C$ has an odd number of vertices, floor or ceiling of half, whichever you prefer] such that $C \setminus A_C$ is nonempty, and every vertex in $C \setminus A_C$ is adjacent to at least one vertex in $A_C$.


 Proof: Assume WLOG that $C$ is a tree. Fix a vertex $y \in C$, and let $Y_1$ be the vertices $y_1$ where the distance from $y$ to $y_1$ in $C$ is an odd integer, and let $Y_2$ be the vertices $y_2$ where the distance from $y$ to $y_2$ is an even integer. As $C$ has at least $2$ vertices, both $Y_1$ and $Y_2$ are nonempty, and partition the vertices of $C$. Take $A_C$ to be as follows:


 - The set $A_C$ is either $Y_1$ or $Y_2$ if $|Y_1|=|Y_2|$.


 - The set $A_C$ otherwise is constructed from first taking the smaller of $Y_1$, $Y_2$, and then add vertices to $A_C$ until $|A_C|$ has the desired size.


 Note that nonemptiness of $C \setminus A_C$ comes from the fact that that $1 \le \lfloor \frac{m}{2} \rfloor \le \lceil \frac{m}{2} \rceil < m$ for each integer $m \ge 2$, and $C$ has at least $2$ vertices. $\checkmark$


 Next, note the following: If $G^c$ has no vertices of degree $0$, then every component of $G^c$ has at least $2$ vertices. Use Claim 1 to arrive at a contradiction, by constructing a set $A$ of $k$ vertices that intersects each component of $G^c$ such that every vertex outside of $A$ is adjacent in $G^c$ to at least one vertex inside of $A$. [To this end, use the fact that, as $G^c$ has an odd number of vertices, that $G^c$ has an odd number $m$ of odd components; for $\lfloor \frac{m}{2} \rfloor$ of the odd components $C$ take ceil of half the vertices, and for the remaining components take floor of half the vertices.] So then conclude that $G^c$ must have at least one component $C$ with $C$ having exactly one vertex $v$, and conclude that $v$ has degree $0$ in $G^c$ and thus degree $2k$ in $G$.

A: Here's what I'd try (so this is necessarily only a hint): Let $V$ be the vertex set. Start with a set $A$ of $k$ vertices, let $v$ be its common neighbor, and let $B=V \setminus (A \cup \{v\})$. Now let $w$ be the common neighbor of $B$. If $w=v$, we're done, else consider $C=V \setminus (B \cup \{w\})$ which is distinct from $A,B$. Repeat this process with $C$...
