1
$\begingroup$

The theorem states: A connected graph has an Euler tour if and only if every vertex has even degree.

But this graph has node 'A' with degree = 3.

Graph image.

Graphed using: http://illuminations.nctm.org/

I think I don't fully understand the workings of the theorem of Euler tours.

$\endgroup$
  • $\begingroup$ What is your definition of "Euler tour"? $\endgroup$ – bof Jun 25 '16 at 10:04
3
$\begingroup$

The theorem says that a connected simple graph has an Euler circuit if and only if each vertex has even degree, and indeed that graph, in which vertices $A$ and $D$ have degree $3$, has no Euler circuit: there is no walk that traverses each edge exactly once and returns to its starting vertex. A companion theorem says that a connected simple graph has an Euler path that is not a circuit if and only if it has exactly two vertices of odd degree, in which case every Euler path begins at one of those two vertices and ends at the other. That's the case for your graph: there are Euler paths, all of which run between $A$ and $D$, but there is no Euler circuit. One such path is $ABDCAFED$, for example.

$\endgroup$
  • $\begingroup$ But what about the circuit, ACDBA and ACDEF, they are circuits and the degree is odd? What am I not understanding? $\endgroup$ – Meticulous Jun 25 '16 at 10:31
  • 1
    $\begingroup$ @K0d3R: An Euler path or circuit by definition traverses every edge of the graph exactly once. Those circuits omit three of the edges altogether. $\endgroup$ – Brian M. Scott Jun 25 '16 at 10:41
  • $\begingroup$ @K0d3R This is why bof asked you what is your definition of Euler tour... $\endgroup$ – Erick Wong Jun 25 '16 at 11:17
  • $\begingroup$ OMG, yes! I understand the whole concept and what I have been wrong about.. Thank you all so much! $\endgroup$ – Meticulous Jun 25 '16 at 11:29
  • $\begingroup$ @K0d3R: You're welcome! $\endgroup$ – Brian M. Scott Jun 25 '16 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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