# (Clarification) A graph with an even number of vertices has two vertices with an even number of common neighbors

I am relatively unfamiliar with mathematics and trying to self-study some topics in graph theory. I've already encountered a proof of this statement on stackexchange (see for example, ∗∗Prove that each graph with an even number of vertices has two vertices with an even number of common neighbors.), and I hope that my question is specific enough to be not a duplicate.

So here is the problem: I have difficulties in understanding exactly when the assumption that $|V(G)|$ is even plays its part in the proof. I believe I am almost there, but I have the feeling that I'm making a mistake somewhere. So, here is how far I've come:

We prove the statement by contradiction. Suppose that all pairs two vertices in the graph have an odd number of common neighbors. Choose an arbitrary vertex $v\in V(G)$, and call the subgraph induced by its neighborhood $H$. For all $x,y\in V(H)$, if $\{x,y\}\in E(G)$, then $y$ is a common neighbor of $v$ and $x$ in $G$. Thus the number of edges in $H$ is equal to the number of common neighbors an vertex in $H$ has with $v$. By assumption this number is odd. But then, it follows from the Handshake Lemma, that the there is an even number of vertices in $H$. And thus the degree of $v$ is even.

Now, consider the number of length-2 walks starting from $v$. This number has to be even. To see why, note that every such walk consist of the triple $(v,k,l)$, where $\{v,k\},\{k,l\}\in E(G)$ (note that $v$ and $l$ are not necessarily distinct vertices). From the above discussion, we know that there are an even number of vertices adjacent to $v$ and that the degree of $k$ is even as well. It follows that the number of length-2 walks starting from $v$, $|W_{v,2}|$, is given as $$|W_{v,2}| = \sum_{k:\{v,k\}\in E(G)} \text{degree}_G(k),$$ which is a sum of even numbers and is therefore even.

But the number of length-2 walks starting from $v$ is also the sum of the length-2 paths starting with $v$ and the length-2 cycles starting from $v$. The latter is equal to the degree of $v$, and is therefore even. The number of length-2 paths starting from $v$ is equal to the number of triples $(v,k,l)$ where $\{v,k\},\{k,l\}\in E(G)$ and $l\ne v$. Note that this implies that $k$ is a common neighbor of $l$ and $v$, the number of which is, by assumption, odd. Thus, the number of length-2 walks starting from $v$ is $$| W_{v,2}| = \text{degree}_G(v) + \sum_{k: \{v,k\},\{k,l\}\in E(G)}\Big(\text{degree}_G(k)-1\Big).$$ The first term is even and the second term is a sum of odd numbers with an odd number of terms. It follows that $|W_{v,2}|$ is odd, a contradiction.

It seems that I've reached a contradiction without using the assumption that $|V(G)|$ is even, which gives me a strong signal that something is wrong. I just can't figure what exactly.

• Consider the complete graph on $3$ vertices. For a given $l$, there are an odd number of candidates for $k$. But how many $l$s are there? – Andrew Woods Jun 29 '17 at 2:41
• @AndrewWoods Thank you for the comment. This is indeed helpful. So, as there are an even number of $l$s, the second term in the last equation is even, and there is no contradiction. Thus, in general, the last term in the last equation should be $\sum_{l \in V(G)\setminus \{v\} }\sum_{k:\{v,k\},\{k,l\}\in E(G)}(\text{deg}_G(k)-1)$. So, the outer sum has an odd number of terms, which leads to a contradiction. Is this correct? – baruuum Jun 29 '17 at 4:36

Thus the number of edges in $H$ is equal to the number of common neighbors an vertex in $H$ has with $v$.

This should be "For each vertex $x$ in $H$, the number of edges $\{x,y\}$ in $H$ is equal to the number of common neighbors between $x$ and $v$."

At the end of your proof, you consider paths $v\to k\to l$. The key insight is that $l$ can be any other vertex in $G$. The assumption was that any two vertices have an odd number of common neighbors, so $v$ and $l$ must have at least $\it1$ common neighbor. Thus, your final sum is over $l$, not $k$. It contains $|V(G)|-1$ terms, and we might not know what they are, but we know that all of them are odd. So if $|V(G)|$ is even, then...