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

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.

2 Answers

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.

• You are disagreeing with the hint where it says an odd number of walks come back to $v$. I agree with you. – Ross Millikan Mar 26 '17 at 23:38

For the first paragraph, consider a vertex $x$ which is a neighbor of $v$. It is part of the subgraph because it is a neighbor of $v$. All the vertices that are common neighbors of $x$ and $v$ are part of the subgraph because they are neighbors of $v$. Within the subgraph $x$ is only connected to vertices that are common neighbors of $x$ and $v$. We are told there are an odd number of those, so within the subgraph $x$ has odd degree. $x$ was arbitrary, so all vertices in the subgraph are odd.

There must be an even number of vertices in the subgraph because the total degree of the subgraph (as any graph) is even by the handshaking lemma. The degree of $v$ is just the number of vertices in the subgraph by the definition of the subgraph. Since $v$ is arbitrary all vertices in the graph must have even degree in the whole graph.

I don't understand the paragraph about walks. The number of walks from $v$ of length $2$ is the sum of the degrees of all the vertices connected to $v$ because we go from $v$ to a neighboring vertex, then to some vertex that vertex is connected to (including $v$). As $v$ has even degree, an even number of walks must return to $v$. The number of returning walks is just the degree of $v$ because you go out and back.