# Graph Theory - Eulerian path

1. Jan 15, 2014

### 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.

Last edited: Jan 15, 2014
2. Jan 16, 2014

### D H

Staff Emeritus
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.

3. Jan 16, 2014

### estro

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

4. Jan 16, 2014

### 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?

5. Jan 16, 2014

### D H

Staff Emeritus
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?

6. Jan 18, 2014

### haruspex

Hi estro,

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

7. Jan 18, 2014

### estro

Hi Haruspex,

I already solved this problem, thanks!

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted