Results 1 to 7 of 7

Math Help - Eulerian graph with even vertices and odd edges

  1. #1
    Newbie
    Joined
    Oct 2007
    Posts
    8

    Eulerian graph with even vertices and odd edges

    Hi guys, i've been set a problem which is to either illustrate a graph which is Eulerian with even vertices and odd edges; or show why no such graph can exist?

    Intuitively im thinking the latter is true, but im struggling to find a sound explanation as to why this is the case. Any help will be appreciated!! thanks a million.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by euler786 View Post
    Which is Eulerian with even vertices and odd edges; or show why no such graph can exist?
    There is a real problem with definitions here. Textbooks and authors do not always agree on the definition of Eulerian Graphs.

    It seems that most current texts agree that an Eulerian graph is one in which there is a closed walk, no edge can be repeated. In this case show that all vertices are even.

    On the other hand, we can find older texts that talk about traceable graphs being Eulerian. That is, there is a walk( not necessarily closed) that includes each edge exactly once. In this case, there are at most two odd vertices.

    So check your text material for the definition in use.
    Last edited by Plato; October 22nd 2007 at 04:33 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2007
    Posts
    8
    A graph is Eulerian if it contains an Euler Tour, an Euler Tour contains a tour where each edge is traversed exactly once, a tour is a closed edge sequence (walk) where each edge is traversed at least once.

    A graph is semi-Eulerian if it contains an Euler Chain, an Euler Chain contains a chain where each edge is traversed exactly once, a chain is an edge sequence (walk) where each edge is distinct.

    A graph is Eulerian if every vertex has even degree. A graph is semi-Eulerian if it contains at most two vertices of odd degree.

    These are the defintions and tests available at my disposal.

    I know intuitively that there can be no graph with an even number of vertices and an odd number of edges and still be Eulerian; but i can't even begin to start a sound argument.

    Thanks for replying Plato
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by euler786 View Post
    I know intuitively that there can be no graph with an even number of vertices and an odd number of edges and still be Eulerian; but i can't even begin to start a sound argument.
    It is not if the number of vertices or edges is even or odd! It is about the degree sequence of the vertices in a connected graph.

    If all the vertices are of even degree (each vertex is concurrent with an even number of edges) then the graph is traceable with a closed path including each edge exactly once. You see that any vertex can be repeated. Thinking a bit more, we realize that if we ‘enter’ a vertex and ‘leave’ it on our walk then the vertex must be even. Moreover, we must begin and end at the same vertex.

    If the connected graph has exactly two odd vertices we can trace it using each edge exactly once. But we must begin at one of the odd vertices and end at the other (again using the in-out reasoning). So that walk cannot be closed.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2007
    Posts
    8
    lol, ok im a bit confused here; the question is;

    'draw a Eulerian graph with an even number of vertices and an odd number of edges; or explain why such a graph can't exist?'

    does that help with any confusion...? i dont think its asking about the degree of the sequences its asking for a total even vertices with a total odd edges...? im not sure now!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2007
    Posts
    8
    Right yes i get you now, thanks for the help mate, have u done this one before..? im finding proofs quite hard, i can a follow a proof and understand it well enough, but i struggle to produce my own, does it just come to you? what do you reckon could help improve this side of my maths...? and once again, thanks for the help, i really do appreciate it.
    gtg bye for now
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    This may be what you are looking for.
    I reread your definitions.
    Attached Thumbnails Attached Thumbnails Eulerian graph with even vertices and odd edges-trac-odd.gif  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 4th 2011, 07:00 PM
  2. Vertices and Edges
    Posted in the Geometry Forum
    Replies: 2
    Last Post: March 23rd 2010, 03:16 PM
  3. Components, edges, and vertices
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2009, 11:35 AM
  4. Edges and vertices of a solid
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 6th 2009, 08:02 AM
  5. Replies: 5
    Last Post: June 22nd 2008, 11:20 PM

Search Tags


/mathhelpforum @mathhelpforum