exercise one

exercise one

אני (guest) 15 Nov 2014 18:47

האם גרף ללא קשתות מכיל מעגל אוילר?
האם גרף עם 4 קודקודים {1,2,3,4}
שמכיל את הקשתות
(1,2)
(2,3)
(3,1)
מכיל מעגל אוילר? גם כאשר הוא מכוון וגם כאשר הוא לא מכוון?

Re: exercise one

Shai V 16 Nov 2014 06:36

Hi,
The answer is yes to all of the above. But those are degenerate examples, that perhaps in other courses might have been used to "trick you" into getting a wrong answer, but we don't do that in this course. We are more interested in teaching you the important things, so we don't usually focus on degenerate cases.
Notice that Euler's theorem is stated for connected graphs only. This is done partially to avoid having to deal with cases like the ones above. In question 3a, you are expected to give an if and only if statement only for strongly connected directed graphs, not for general directed graphs.
It is possible, of course, to completely formulate these statements for general graphs, but the formulations become unnecessarily cumbersome, and we usually ignore them (at least in some sense), so that we will have time to focus on more important things.