Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Do you know the definitions of both of those terms? –  MITjanitor Mar 10 '13 at 22:20
5  
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. –  Brian M. Scott Mar 10 '13 at 22:25
    
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! –  Gerry Myerson Mar 10 '13 at 23:03

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.