Can a graph with no self loops and odd common neighbors have an Eulerian path?

[estro]

I'm trying to prove that a graph with the below properties has an eulerian path.
1. Graph has no self loops or parallel edges.
2. Every two different vertices u and v have an odd number of common neighbor vertices.

I'm thinking about this problem for a whole day and can't manage to prove this. I think that I can prove it if I could prove that every graph with these properties must have odd number of vertices but I can't prove it as well.

 

[D H]

As I read it, your conjecture is easily falsified by a trivial modification to the seven bridges of Königsberg problem. Using the word "odd" is rather odd as one of the conditions for an undirected graph to have an Eulerian cycle is that every vertex must have an even degree.

 

[estro]

The number of common neighbor vertices is odd, however don't forget about not common vertices.

 

[haruspex]

Looks like it will involve proving all vertices have even degree. So consider a vertex of odd degree. What can you say about its neighbours and the edges connecting them?

 

[D H]

What, exactly, do you mean by "Every two different vertices u and v have an odd number of common neighbor vertices", and how does the bridges of Königsberg problem (which does not have an Eulerian path) not exhibit this behavior?

 

[haruspex]

Hi estro,

Are you still interested in this? The hint I gave in post #4 does lead to the solution.

 

[estro]

Hi Haruspex,

I already solved this problem, thanks!