Tried a lot of things and was a bit disappointed that this was the method that ended up working, but still a nice problem. Let each person be a vertex on a graph G, and let two vertices share an edge if they are friends. Setting up a double count on every pair of people, we get, $$\sum_{i=1}^{2017} \binom{\text{deg}(v_i)}{2}=\binom{2017}{2}$$Similarly, for any subgraph $G'$ with $n$ vertices, $$\sum_{v_i\in G'} \binom{\text{deg}(v_i)}{2}\le \binom{n}{2}$$where $\text{deg}$ measures the degree within that subgraph. Using the equality above there must exist a vertex with $n\ge 46$ edges - call this vertex $v_1$. Let the $n$ vertices adjacent to $v_1$ be "good," and let the rest of the vertices be "bad." (Except $v_1$ itself which is neither good nor bad.) Call a pair of vertices that have exactly one common adjacent vertex "compatible." First, note that every vertex must be adjacent to exactly one good vertex so that every vertex is compatible with $v_1$. Then, the subgraph of good vertices is exactly a perfect matching. Thus, for each bad vertex to be compatible with all of the good vertices, each bad vertex must be adjacent to at least $n-1$ other bad vertices. Now, consider the subgraph $G_b$ of bad vertices. We have, $$\sum_{v_i\in G_b} \binom{\text{deg}(v_i)}{2}\ge (2016-n)\binom{n-1}{2}$$So from above $n$ must satisfy, $$(2016-n)\binom{n-1}{2}\le \binom{2016-n}{2}$$And the only $n\ge 46$ that satisfies this inequality is $n=2016$. Thus, $v_1$ has $2016$ friends, and it directly follows using our first equation that every other person has exactly $2$ friends. Thus, the smallest (and only?) possible difference is $\boxed{2014}$.

Of course you have to build a construction, but it's easy. Consider a graph with vertices $V$ and $A_i,B_i$, where $1\leq i\leq 1008$. The edges are $A_iB_i$, $A_iV$ and $B_iV$ for all $1\leq i\leq 1008$.

This is a theorem

laegolas wrote: Let the $n$ vertices adjacent to $v_1$ be "good," and let the rest of the vertices be "bad." laegolas wrote: Thus, for each bad vertex to be compatible with all of the good vertices, each bad vertex must be adjacent to at least $n-1$ other bad vertices. I thought we have $n$ good vertices, so isn't the second quote telling the false statement? In my opinion it should be Thus, for each bad vertex to be compatible with all of the good vertices, each bad vertex must be adjacent to at least $n$ other bad vertices.

rafayaashary1 wrote: This is a theorem Can you give me theorem that ?

Maybe this paper? https://pdfs.semanticscholar.org/d724/f9a4fd5dee38a54cd838d33a6a425f449387.pdf

thank you sunfishho

https://artofproblemsolving.com/community/c6h269248p1459064