0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Andrew Woods Jun 29 '17 at 2:41
  • $\begingroup$ @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? $\endgroup$ – baruuum Jun 29 '17 at 4:36
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.