1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory - Eulerian path

  1. Jan 15, 2014 #1
    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. jcsd
  3. Jan 16, 2014 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Jan 16, 2014 #3
    The number of common neighbor vertices is odd, however don't forget about not common vertices.
     
  5. Jan 16, 2014 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  6. Jan 16, 2014 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
  7. Jan 18, 2014 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Hi estro,

    Are you still interested in this? The hint I gave in post #4 does lead to the solution.
     
  8. Jan 18, 2014 #7
    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



Similar Discussions: Graph Theory - Eulerian path
  1. Graph Theory (Replies: 5)

  2. Graph theory (Replies: 0)

  3. Graph Theory (Replies: 2)

  4. Graph Theory (Replies: 0)

  5. Graph Theory (Replies: 4)

Loading...