I showed this on http://www.mathlinks.ro/viewtopic.php?t=68109 . Very nice problem.

**EDIT:** Let me repeat the solution I gave at the above link, seeing that AoPS isn't great at printability.

I'll prove the contrapositive of the question:

**Theorem 1.** Let $n$ be a positive integer. Let $S$ be a graph with $2n$ vertices. Then, $S$ has two distinct vertices which have an even number of common neighbors.

Here, graphs are assumed to be finite and loopless.

Theorem 1 is problem 14.10 in Arthur Engel's *Problem-Solving Strategies*. My proof (more or less the same as Engel's one) relies on the following well-known fact (a particular case of the handshaking lemma):

**Theorem 2.** If a graph has an odd number of vertices, then it has a vertex with even degree.

*Proof of Theorem 1.* We assume that our graph $S$ is a simple graph (since multiple edges don't matter for this theorem). The *degree* of a vertex in a simple graph will mean the number of its neighbors, or, equivalently, the number of edges starting at this vertex.

We are in one of the following two cases:

*Case 1:* Some vertex $C$ of the graph $S$ has an odd degree.

*Case 2:* Every vertex of the graph $S$ has an even degree.

Let us first consider Case 1. In this case, some vertex $C$ of the graph $S$ has an odd degree. Consider such an $C$. Thus, the vertex $C$ has an odd degree, i.e., an odd number of neighbors. Let $S'$ be the subgraph of $S$ whose vertices are the neighbors of $C$ (and whose edges are only those edges of $S$ whose both endpoints are neighbors of $C$). Thus, this subgraph $S'$ has an odd number of vertices (since $S$ has an odd number of neighbors). Hence, by Theorem 2, this subgraph $S'$ must have a vertex of even degree. Consider such a vertex, and denote it by $D$. Thus, the vertex $D$ has an even degree in the subgraph $S'$. In other words, the number of neighbors of $C$ that are also neighbors of $D$ is even. In other words, the number of common neighbors of the two distinct vertices $C$ and $D$ is even. Hence, Theorem 1 is proven in Case 1.

Now, let us consider Case 2. In this case, every vertex of the graph $S$ has an even degree. Pick an arbitrary vertex $A$ of the graph $S$. (Here, we are using the fact that $n$ is a positive integer, so that $S$ has a vertex to begin with.) Construct a subgraph $S'$ of $S$ as follows:

The vertices of $S'$ should be all the $2n$ vertices of the graph $S$ except of the vertex $A$.

The edges of $S'$ should be those edges of the graph $S$ that contain a neighbor of $A$ but not the vertex $A$ itself. (In other words, an edge of $S$ is an edge of $S'$ if and only if at least one of the endpoints of this edge is a neighbor of $A$; the other endpoint can be arbitrary, but it cannot be $A$ since $A$ is not a vertex of $S'$.)

Then, the graph $S'$ has an odd number of vertices ($2n - 1$ vertices, to be precise). Hence, Theorem 2 shows that this graph $S'$ has a vertex $D$ with even degree. Consider this vertex $D$. Hence, $D$ is a vertex of $S$ distinct from $A$.

The vertex $D$ has an even degree in the graph $S$ (since we are in Case 2); in other words, there is an even number of edges of the graph $S$ that contain $D$. Let this number be $2k$ (with $k$ being a nonnegative integer). Thus, we know that exactly $2k$ edges of $S$ contain $D$.

If $D$ was a neighbor of $A$ in $S$, then all of these $2k$ edges would be edges of the subgraph $S'$, except for the edge that joins $D$ to $A$; thus, there would be a total of $2k-1$ edges in $S'$ that contain $D$; in other words, the degree of $D$ in the graph $S'$ would be $2k-1$. This would contradict the fact that the degree of $D$ in the graph $S'$ is even (since $2k-1$ is not even). Thus, $D$ cannot be a neighbor of $A$ in $S$. Therefore, the edges of $S'$ that contain $D$ are precisely the edges of $S$ that contain $D$ and a neighbor of $A$. Hence, the degree of $D$ in the subgraph $S'$ is the number of common neighbors of the vertices $A$ and $D$ in the graph $S$. Since this degree is even, we thus see that the two distinct vertices $A$ and $D$ have an even number of common neighbors. Hence, Theorem 1 is proven in Case 2.

We thus have proven Theorem 1 in both Cases 1 and 2; so the proof is complete. $\blacksquare$