Results 1 to 2 of 2

Math Help - eulerian graph

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    10

    eulerian graph

    Prove or disprove: There is no Eulerian graph with an even number of vertices and an odd number of edges.



    from what i understand i think this statement is true. u cant have an eulerian graph with an even number of vertices and an odd number of edges. but im not sure how to prove this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,381
    Thanks
    1474
    Awards
    1
    Quote Originally Posted by demon1 View Post
    Prove or disprove: There is no Eulerian graph with an even number of vertices and an odd number of edges.
    Here are facts.
    If a graph is Eulerian then it is connected and each vertex is even.
    The degree sum is twice the number of edges.
    An even number times an even number is a multiple of four.

    Now you can prove it by putting those together.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of being Eulerian
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 13th 2011, 02:40 AM
  2. Eulerian and hamiltonian questions
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: October 13th 2010, 07:03 AM
  3. Replies: 1
    Last Post: October 13th 2010, 03:58 AM
  4. [SOLVED] Eulerian graphs
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 13th 2010, 10:40 AM
  5. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 03:12 PM

Search Tags


/mathhelpforum @mathhelpforum