# Euler Path and Graph

• May 26th 2009, 03:08 AM
kurac
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).
• May 26th 2009, 03:17 AM
kurac
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.
• May 26th 2009, 03:37 AM
Swlabr
Quote:

Originally Posted by kurac
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.
• May 26th 2009, 05:12 AM
TiRune
Two not-connected squares?
• May 26th 2009, 07:00 AM
Swlabr
Quote:

Originally Posted by TiRune
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.