# Let $G$ be a graph such that for all $u, v ∈ V (G)$, $u \ne v$, $|N (u) ∩ N (v )|$ is odd. Then show that the number of vertices in $G$ is odd

After working for sometime I figured out the following course of action. (from a few sample cases on 4 and 5 vertices)

i) I wanted to prove that the graph had no odd degree vertex.

ii) There exists at least one vertex adjacent to all other vertices.

If I can do these, then if $$n = |G|$$, $$(n-1)$$ is even - hence, $$n$$ is odd.

My friend told me that by considering a typical vertex and its neighbours and considering the subgraph induced on it, he has been able to prove the 1st part.

So now to prove the 2nd part, I was cosidering a vertex with maximum degree and if it does not have the above property I wanted to derive a contradiction.

But I think I am stuck.

Any suggestions?

You've already shown that every vertex $$v$$ has even degree, for if it had odd degree, than look at its set of neighbors with the induced subgraph structure, $$H$$. $$H$$ has an odd number of vertices with every vertex having odd degree, which is a contradiction.

Now, consider the adjacency matrix $$A$$ of $$G,$$ where we consider a vertex to be adjacent to itself. Then the condition of $$|N(u)\cap N(v)|$$ being odd translates to $$A^2=F,$$ where $$F$$ is the matrix with each entry being 1. Since every vertex of $$A$$ has even degree, we have the identity $$AF=F$$. Therefore $$F^2=FA^2=F$$. The identity $$F^2=F$$ exactly means that the number of vertices is odd. This completes the proof.

• Very nice, but you should have added that the adjacency matrix that you construct is over F_2 rather than over Q. – darij grinberg Mar 6 '10 at 17:53
• right you are. my bad :) – jacob Mar 6 '10 at 23:21
• Good answer. I'd replace $FA^2$ by $A^2 F$ to make it slightly clearer. – Tony Huynh Mar 8 '10 at 19:33

Jacob seems to have beaten me to it by a few minutes, but an algebraic graph theory proof works nicely, so I'll add my slight variant.

If $A$ is the $n \times n$ adjacency matrix of the graph, which we assume has no odd degree vertices, then over $Z_2$ the condition shows that $A^2$ has 0s on the diagonal and 1s elsewhere - i.e. that $A^2 = J - I$.

But (again over $Z_2$) $J-I$ has rank $n$ if $n$ is even. But $A$ does not have full rank as $A j = 0$ where $j$ is the all-ones vector (because graph has no odd degree vertices), and so neither can $A^2$.

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$$

It's not true, though, is it? The graph with no vertices satisfies your property vacuously and has an even number of vertices.

• +1, since such trivial cases may lead into trouble when taken too lightly. – darij grinberg Mar 6 '10 at 17:54
• @darij grinberg : Yet you must show that that this is not significant : Is the empty graph an initial object in the category of graphs ? In which respect does and empty set have an even number of elements ? – Jérôme JEAN-CHARLES Nov 21 '11 at 14:36

I proved over here that statement ii) holds when we make the stronger assumption that $|N(u) \cap N(v)|$ is exactly $1$ for every $u, v$.

Most of the argument probably does not generalize, but at least one piece of it does. That part is that if $G$ is a minimal counterexample, then the complement graph is connected. I'll prove this by contradiction:

Let $X$ and $Y$ be a partition of the vertices into two nonempty parts such that every vertex in X is connected to every vertex in Y. If $X$ has even size, then we see that $Y$ has the same property $G$ has and is smaller than $G$, so $Y$ has odd size and $G$ has an odd number of vertices. If $X$ has odd size, then if we collapse $X$ to a point $x$ we still have the property that $|N(u) \cap N(v)|$ is odd for $u, v$ in $Y$, and also for any $u$ in $Y$, $|N(x)\cap N(u)|$ is odd by your step i), so $Y\cup x$ satisfies the same properties $G$ does and contains a vertex that is connected to everything, so $Y\cup x$ has odd size, so $G$ has odd size.

Unfortunately, I can't see any obvious nice relationship that must be satisfied by two nonadjacent vertices in our graph $G$...