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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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$

Answer 4

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

Answer 5

I'm rather late to the party but hope to present a somewhat brief proof which is closer to the OP's intended method.

It is nearly identical to a double counting proof which I found here: https://math.stackexchange.com/questions/2204508/%E2%88%97%E2%88%97prove-that-each-graph-with-an-even-number-of-vertices-has-two-vertices-with-an

It is has been well established that the degree of every vertex must be even; briefly, this is because if $v\in V(G)$ were an odd vertex, then every vertex $u \in [N(v)]$ would have odd degree $d(u)|_{[N(v)]} = |N(u)\cap N(v)|$ in the induced subgraph of $N(v)$ in $G$, which I have denoted by $[N(v)]$. This gives rise to a graph with an odd number of odd vertices, a contradiction.

Now, we count the number of walks of size 2 from a vertex $x \in V(G)$ to any other vertex in $G$. Note that we may always find such a walk, since $\forall u,v \in V(G), |N(u) \cap N(v)| \not = 0$.

One one hand, the number of such walks must be even. This is because if $y \in N(x)$, since the degree of $x$ is even, the number of walks, which is given by $\sum_{y\in N(x)} (d(y)-1)$, must be an even number (because the sum of an even number of odd numbers must be even).

Another way to count the number of such walks, is to consider the set as a whole. Having chosen some vertex $x \in V(G)$, there are $|V(G)| - 1$ other vertices to which $x$ can form a path of size 2 to. The number of such walks is then $\sum_{z \in V(G)-\{x\}} |N(x) \cap N(z)|$. If $|V(G)| - 1$ were an odd number, then this sum would be odd, since the sum of an odd number of odd numbers is odd; a contradiction.

Therefore, $|V(G)| - 1$ must be even, and $|V(G)|$ is odd.

Answer 6

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