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

Solution 1:

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.

Solution 2:

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.