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

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

Answer 4

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

Answer 5

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