Let $G$ be a graph in which every pair of vertices has an odd number of common neighbors.
Prove that $G$ is Eulerian.
I have in mind two main ways to prove this but every time I get stuck.
-
Get a contradiction to odd number of neighbors by assuming there are even number of nodes of odd degree, so I pick two nodes of odd degree and try to get a contradiction from the fact that they have an odd number of neighbors but can't find anything "wrong".
-
Build a line graph $L(G)$ where all the nodes correspond to vertices of $G$
and try to find a Hamilton cycle using the standard theorems …. (Dirac , Ore…).
It looks like a legit way since the graph $G$ has high "connectivity" (any two nodes have at least $1$ common neighbor so you can get from any node to any node by passing only $2$ vertices) but still can't deduce that the degree on the nodes in the $L(G)$ are high "enough" to use any of the theorems (by high enough I mean either the prerequisite for Ore: $d(u)+d(v) \ge n$ or in case of Dirac $\delta(L(G)) \ge \frac{n}{2}$)
It's a homework question so I would prefer an idea for the solution instead of the full answer.
Best Answer
What you want to do is prove that every vertex has even degree.
Assume that one vertex, $v$, has odd degree. You know that it has an odd number of common neighbours with every other edge. This means that if it is adjacent to vertices $\{v_1, \dots v_i \}$, then it is adjacent to vertex $v_1$ and and odd number of other vertices, vertex $v_2$ and an odd number of other vertices and so on. These sets of adjacent vertices must of course overlap. What can you say about the sizes of the overlaps if the degree of $v$ is odd? How does this lead you to a contradiction?