Results 1 to 6 of 6

Math Help - Graph theory regarding cycles

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    42

    Graph theory regarding cycles

    Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by dynas7y View Post
    Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle?
    You know that twice the number of edges equals the degree sum.
    Does this mean that the number of edges is the number of edges?
    So what is the conclusion?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    42
    What do you mean by is the number of edges the number of edges? Using the theorem to find the number of edges the number of edges would be 2n/2, where n is the number of vertices. So if n is odd then there are an odd number of edges and if n is even there are an even number of edges...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by dynas7y View Post
    What do you mean by is the number of edges the number of edges? Using the theorem to find the number of edges the number of edges would be 2n/2, where n is the number of vertices. So if n is odd then there are an odd number of edges and if n is even there are an even number of edges...
    If a simple graph has n vertices, |E| is the number of edges, and \text{deg}(v_k) is the degree of vertex v_k
    then  2\left| E \right| = \sum\limits_k {\deg (v_k )} .

    That is a most basic idea in graph theory.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    42
    I understand the theorem, which is what I explained in my post regarding the sum of the degrees and the number of edges. By the theorem, since each vertex has degree 2, then the number of vertices multiplied by 2 gives the sum of the degrees. Divide this by two gives you the number of edges. I'm not sure how this relates to the original question though of whether a graph with all of it's vertices having degree 2 is necessarily a cycle
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by dynas7y View Post
    I understand the theorem, which is what I explained in my post regarding the sum of the degrees and the number of edges. By the theorem, since each vertex has degree 2, then the number of vertices multiplied by 2 gives the sum of the degrees. Divide this by two gives you the number of edges. I'm not sure how this relates to the original question though of whether a graph with all of it's vertices having degree 2 is necessarily a cycle
    I must say that I do not think that understands the implication of this material.
    Every vertex has two concurrent edges.
    There are no other possibilities.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. No. of cycles in graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 1st 2012, 01:55 AM
  2. [SOLVED] Set Membership Cycles: The Axiom of Regularity in ZF Set Theory.
    Posted in the Discrete Math Forum
    Replies: 83
    Last Post: July 27th 2010, 03:28 AM
  3. graph theory question about walks and cycles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 29th 2010, 08:44 PM
  4. Cycles of a de Bruijn graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 18th 2010, 08:26 AM
  5. Cycles in an undirected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 12:30 AM

Search Tags


/mathhelpforum @mathhelpforum