co.combinatorics - Let G be a graph such that for all u, v ∈ V (G), u no equal to v , |N (u) ∩ N (v )| is odd. Then show that the number of vertices in G is odd

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 $Ycup x$ satisfies the same properties $G$ does and contains a vertex that is connected to everything, so $Ycup 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$...

• Next the sun - Does Dark Matter affect the motion of the Solar System?
• Previous Why are Lie Algebras/ Lie Groups so much like crossed modules, and not?