Results 1 to 9 of 9
Like Tree1Thanks
  • 1 Post By tinabaker

Math Help - graphs

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    graphs

    Hello

    I have a couple questions about graphs that I am not sure about...

    1. If a graph contains a cycle that includes all the edges, the cycle is an Euler cycle. My answer: Yes, by the definition of the Euler cycle - a cycle in a graph G that includes
    all of the edges and all of the vertices of G is called an Euler cycle.

    2. Find a formula for the number of edges in Km,n . Answer: m*n. But not sure how to prove that...

    3.Find a formula for the number of edges in Kn . Answer: (n(n-1))/2. But not sure how to prove that...

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: graphs

    Quote Originally Posted by tinabaker View Post
    1. If a graph contains a cycle that includes all the edges, the cycle is an Euler cycle. My answer: Yes, by the definition of the Euler cycle - a cycle in a graph G that includes
    all of the edges and all of the vertices of G is called an Euler cycle.
    No, this is an incorrect definition of a Euler cycle.

    Quote Originally Posted by tinabaker View Post
    2. Find a formula for the number of edges in Km,n . Answer: m*n. But not sure how to prove that...
    Use the rule of product: first select a vertex in one set and then a vertex in the other set to which it is connected.

    Quote Originally Posted by tinabaker View Post
    3.Find a formula for the number of edges in Kn . Answer: (n(n-1))/2. But not sure how to prove that...
    Each vertex has n - 1 adjacent edges. This counts each edge twice.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: graphs

    thank you for help with 2 and 3! but ...hm...the definition of an Euler cycle is from my book.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: graphs

    Quote Originally Posted by tinabaker View Post
    the definition of an Euler cycle is from my book.
    Would you mind writing a direct quotation from your book? I also thought the answer to the first question is yes at first, but then I reviewed the definition and saw that there is a difference.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: graphs

    I copied and pasted here.
    "In honor of Euler, a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler cycle." (page 391) Discrete Mathematics, Seventh Edition
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: graphs

    OK, my bad. Apparently, the definition of a cycle in your book requires that vertices are not repeated. Wikipedia says this here: "Like path, this term [cycle] traditionally referred to any closed walk, but now is usually understood to be simple [i.e., no vertices (and thus no edges) are repeated] by definition." The reason I objected was that Euler cycle includes each edge exactly once. But if a cycle includes any edge no more than once by definition, then it is possible to say that Euler cycle is a cycle that contains all edges.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: graphs

    Spasibo.
    P.S. Are you russian?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: graphs

    Pozhaluista. Yes.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: graphs

    ochen' prijatno poznakomitsja s takim ymnym chelovekom:-)
    Thanks from emakarov
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: December 29th 2009, 09:08 PM
  2. log graphs
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 22nd 2009, 05:01 PM
  3. 3d Graphs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 16th 2008, 12:21 PM
  4. Graphs
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 16th 2007, 11:36 PM
  5. Help with graphs
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: October 20th 2007, 11:03 PM

Search Tags


/mathhelpforum @mathhelpforum