-
Notifications
You must be signed in to change notification settings - Fork 0
Home
An Euler path, in a graph or multigraph, is a walk through the graph which uses every edge exactly once. It starts and ends at different vertices. Suppose that a graph has an Euler path P. For every vertex v other than the starting and ending vertices, the path P enters v the same number of times that it leaves v (say n times). Therefore, there are 2n edges having v as an endpoint. Therefore, all vertices other than the two endpoints of P must be even vertices. Therefore, if a graph G has an Euler path, then it must have exactly two odd vertices.
An Euler circuit is a circuit that uses every edge of a graph exactly once. It starts and ends at the same vertex. Suppose that a graph G has an Euler circuit C. For every vertex v in G, each edge having v as an endpoint shows up exactly once in C. The circuit C enters v the same number of times that it leaves v (say n times), so v has degree 2n. That is, v must be an even vertex. Therefore, if a graph G has an Euler circuit, then all of its vertices must be even vertices.