Results 1 to 3 of 3

Math Help - graph theory

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    36

    graph theory

    prove that a closed walk of odd length contains a cycle.

    i am able to proceed upto this stage:

    a closed walk may be like this v1,v2,........,v1

    now,if all the points are distinct in the walk,then the given walk represents a cycle.

    & if suppose a point,say v, is the first point in the walk to be repeated,then if we start from the first v to the repeated v then it will form a cycle.

    but i am not able to understand why a closed walk of odd length is required.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Consider the walk v_1v_2v_1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    36

    @above

    but then again,

    if we consider a walk v1,v2,v3,v2,v4,v1 like this,then it will again not have any cycle.

    so,i think v2,v3,v2 is to be considered a cycle of length 1 or 2,even though it is not defined.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum