I'm trying to prove that if a graph has an Eulerian path, then the number of odd degree vertices is either 0 or 2.
My attempt.
We know that the sum of the degrees of all vertices is twice the number of edges. Mathematically, for a graph G:
$$\sum_{v \in V(G)} \text{deg}(v) = 2|E(G)|$$
Now, let's consider a graph that has an Eulerian path. An Eulerian path is a path that visits every edge of the graph exactly once.
Property 1. In an Eulerian path, every vertex except for the starting and ending vertices must have an even degree. This is because, during the traversal, each time we enter a vertex, we also exit it, so the degree of the vertex should be even.
Property 2. The starting and ending vertices of the Eulerian path must have odd degrees. The starting vertex has one more outgoing edge, and the ending vertex has one more incoming edge compared to the other vertices.
Now, let's use these properties to prove the statement. If a graph has an Eulerian path, there must be exactly two vertices with odd degrees (the starting and ending vertices) and all other vertices must have even degrees.
-
If the number of odd-degree vertices is 0, then all vertices have even degrees, which is fine.
-
If the number of odd-degree vertices is 2, then there are exactly two vertices with odd degrees, which is also fine.
In all other cases, if there are more than 2 odd-degree vertices, there cannot be an Eulerian path because, in that case, at least one vertex (other than the starting and ending vertices) will have an odd degree, which contradicts Property 1.
So, we have shown that if a graph has an Eulerian path, then the number of odd-degree vertices is either 0 or 2.
Best Answer
Taking into account the comments, we can fix and simplify the proof from the question as follows.
Every vertex except for the start and end vertices has an even degree, because each time we enter the vertex, we also exit it. Since the sum of the degrees of all vertices is twice the number of edges, there cannot be exactly one vertex of odd degree.