[Math] ∗∗Prove that each graph with an even number of vertices has two vertices with an even number of common neighbors.

graph theory

By contradiction. Suppose that any two vertices have an odd number of common neighbors. For an arbitrary vertex $v$, look at the subgraph induced by the neighbors of $v$. All degrees in this subgraph are odd(why all degrees are odd here?),

and hence the degree of $v$ is even(it is even because of the handshaking theorem?).

Let us count walks of length $2$ beginning at $v$. Their total number is even (because every vertex has an even degree). At the same time, an odd number of these walks come back to $v$, but any other vertex is reached by an odd number of walks, and hence the number of vertices distinct from $v$ must be even—a contradiction.

Please help me visualize this hint from my textbook.

Best Answer

Step 1. Suppose that any two vertices have an odd number of common neighbors. For an arbitrary vertex $v$, look at the subgraph induced by the neighbors of $v$. All degrees in this subgraph are odd.

Let $G$ be the original graph, and let $H$ be the induced subgraph of neighbors of $v$. If $xy$ is an edge of $H$, then back in $G$, $y$ is a common neighbor of $x$ and $v$: it's a neighbor of $x$ because $xy$ is also an edge of $G$, and it's a neighbor of $v$ because everything in $H$ is.

Conversely, whenever $x$ is a neighbor of $v$ and $y$ is a common neighbor of $x$ and $v$, $xy$ is an edge of $H$.

So for some vertex $x$ in $H$, the number of edges $xy$ is the number of common neighbors of $x$ and $v$; by assumption, this is odd.

Step 2. ...and hence the degree of $v$ is even.

You're right; this is because of the handshake lemma, applied to $H$. We know $H$ has an even number of vertices of odd degree; all of $H$'s vertices have odd degree, so $H$ has an even number of vertices. But the number of vertices in $H$ is precisely the degree of $v$.

Step 3. Let us count walks of length $2$ beginning at $v$...

A walk beginning at $v$ is any triple $(v,w,x)$ where $vw$ and $wx$ are edges of $G$. Why is the number of walks even? For every choice of $w$, we have $\deg w$ many choices for $x$. So the number of walks is $\sum_{w} \deg w$, where the sum ranges over all $w$ adjacent to $v$. Each term in the sum is even, so the number of walks is even.

We can also count the walks in a different way. We have:

  • walks $(v,w,v)$ that come back to $v$. There are $\deg v$ of these: an even number.
  • walks $(v,w,x)$ for another vertex $x \ne v$. There are $|V(G)| - 1$ choices of $x$. For each $x$, the number of choices for $w$ is the number of common neighbors that $v$ and $x$ have, which is odd by assumption.

If $|V(G)|$ were even, then there would be an odd number of walks of the second kind: $|V(G)|-1$ is an odd number of choices, and each results in an odd number of options for $w$. But then there's an odd number of walks, and we've already proved that there's an even number of walks.

So $|V(G)|$ must be odd, and we're done.

Related Question