Results 1 to 5 of 5

Math Help - Euler Path and Graph

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    Euler Path and Graph

    Hi,

    Is it possible to have a graph with 8 vertices such that the degree of each vertex is 2 yet the graph does not have euler path.

    Im trying to draw a graph that shows this. But it seems impossible since the degree of each vertex must be even (2).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    A graph has an Euler path if and only if all vertices but precicely two have even degree.

    I found this on an old thread.

    So a possible answer to this question could simply be a circle that is connected by 8 vertices. Correct? Since there is no 2 vertices in the graph that DONT have even degree.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by kurac View Post
    A graph has an Euler path if and only if all vertices but precicely two have even degree.

    I found this on an old thread.

    So a possible answer to this question could simply be a circle that is connected by 8 vertices. Correct? Since there is no 2 vertices in the graph that DONT have even degree.
    I'm presuming that that quote is by me (I said that last week in a thread), and so I should probably make myself more precise - a graph has an Euler path but not an Euler circuit if and only if all vertices but precicely two have even degree.

    I believe Eulerian graphs are a sub-class of semi-Eulerian graphs. I may, of course, be completely wrong.

    Thus, we have two answers depending on our definition. Either it is not possible or every such graph has an Eulerian path.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    May 2009
    From
    Tokyo, Japan
    Posts
    46
    Two not-connected squares?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by TiRune View Post
    Two not-connected squares?
    Drat! I was meaning to look to see if the graph was connected or not, and then got waylayed on definitions. Good answer though.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph problem(euler,hamilton,color)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 4th 2011, 12:10 AM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 08:18 PM
  3. Replies: 0
    Last Post: April 28th 2010, 10:26 PM
  4. Replies: 0
    Last Post: February 20th 2010, 08:26 AM
  5. Replies: 3
    Last Post: May 27th 2009, 06:58 PM

Search Tags


/mathhelpforum @mathhelpforum