Subject: Euler Confusion
From: "William J. Rapaport"
Date: Mon, 7 Dec 2009 13:30:38 -0500 (EST)
A student writes:
"Today in class you told us that
1. All vertices of an Euler Circuit are always of even degree
2. Exactly 2 vertices of any Euler Path are always of odd degree
3. An Euler Circuit is an Euler Path (that starts and ends at the same vertex)
The theorems tell us that circuits and paths must be different, but the
definition of the circuit tells us it is a path. Was one of these
theorems or the definition incomplete?"
Reply:
Good catch! The correct statement of Thm 2, as given on p.637 is:
"A connected multigraph has an Euler path *but not an Euler circuit*
iff
it has exactly 2 vertices of odd degree"