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).
Printable View
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).
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.Quote:
Originally Posted by kurac
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.
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.Quote:
Originally Posted by TiRune