Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple graph theory

  1. Oct 29, 2008 #1
    Hello! This question seems simple but I think I'll need your help to prove it.

    Prove that if there are vertices x and y in V(G) such that G contains three independent x-y paths then G contains an even cycle.

    Thank you in advance.
  2. jcsd
  3. Oct 30, 2008 #2


    User Avatar
    Science Advisor

    Hint: The paths are either odd or even.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook