1
$\begingroup$

Could someone help explain to me how I can figure out if the graphs given are Euler cycle or Euler path? Is it through trial and error?

Here are some examples:

enter image description here

Would appreciate any help.

$\endgroup$
3
  • 3
    $\begingroup$ Do you know the definitions of both of those terms? $\endgroup$
    – MITjanitor
    Mar 10, 2013 at 22:20
  • 5
    $\begingroup$ There’s a very simple test for whether a graph has an Euler circuit or path; if you’re studying the topic in a course, I’d expect this test to have been presented. HINT: It has to do with the degrees of the vertices of the graph. $\endgroup$ Mar 10, 2013 at 22:25
  • $\begingroup$ And if you haven't seen the test to which @Brian refers, trial and error is not a bad substitute for these small graphs --- you may discover the test yourself! $\endgroup$ Mar 10, 2013 at 23:03

2 Answers 2

5
$\begingroup$

Look at the number of odd-degree vertices in each graph...

  • 0 means there is at least 1 Euler circuit,
  • 1 means it is impossible,
  • 2 means there is no Euler circuit but there is at least 1 Euler path,
  • more than 2 means there are neither in the graph...

Hope that helps.

http://www.ctl.ua.edu/math103/euler/howcanwe.htm

$\endgroup$
2
$\begingroup$

a graph is Eulerian if its contains an Eulerian circuit, where Eulerian circuit is an Eulerian trail. By eulerian trail we mean a trail that visits every edge of a graph once and only once. now use the result that "A connectded graph is Eulerian if and only if every vertex of G has even degree." now you may distinguish easily. You must notice that an Eulerian path starts and ends at different vertices and Eulerian circuit starts and ends at the same vertex.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .