1. Not finding help here? Sign up for a free 30min 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 proof

  1. Jan 14, 2016 #1
    1. The problem statement, all variables and given/known data
    Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree.

    2. Relevant equations


    3. The attempt at a solution
    If every vertex in a graph G has degree two or greater, then there is always a way to get in and out without using the same edge. If we start at any vertex and try to traverse the graph by using the rule of getting in and out and not using the same edge, eventually we will realize that we can't stop, so this implies that there is a cycle. Therefore G can't be a tree.

    I am new to this types of proofs, so I need feedback.
     
    Last edited: Jan 14, 2016
  2. jcsd
  3. Jan 15, 2016 #2

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Consider the following graph:
    gaph.jpg
    Apply your proof to vertex 1. Does it show that there is a cycle through vertex 1?
     
  4. Jan 15, 2016 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's not just a counterexample to the proof, it's a counterexample to the given claim.
     
  5. Jan 15, 2016 #4

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    I know, it was a not too subtle hint. :oldsmile:
    The "each vertex" in the statement of the exercise must be an error, and the exercise was probably something like: "prove that the graph contains a cycle".
     
  6. Jan 15, 2016 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that makes sense for the last part.
     
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 proof
  1. Graph Theory Proof (Replies: 1)

  2. Graph theory proof (Replies: 11)

  3. Graph theory proof (Replies: 22)

Loading...