1
$\begingroup$

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.

  1. If the number of odd-degree vertices is 0, then all vertices have even degrees, which is fine.

  2. 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.

$\endgroup$
3
  • 1
    $\begingroup$ "The starting and ending vertices of the Eulerian path must have odd degrees" - is not true. Hence neither is "If a graph has an Eulerian path, there must be exactly two vertices with odd degrees" $\endgroup$ Oct 14, 2023 at 9:17
  • $\begingroup$ OK, maybe I can simplify my proof as follows. A vertex that is not a start or an end vertex must have even degree (otherwise, once I enter the node, I wouldn't be able to exit to continue my path). For the same reason, an odd degree vertex must be a start or an end vertex. Since we have one start and one end, then I prove at least the part of 2 odd degree vertices. What do you think? $\endgroup$
    – Mark
    Oct 14, 2023 at 10:16
  • $\begingroup$ On an Eulerian path, the starting node and the ending node can be the same, and all nodes have an even degree. You can say that there are at most two nodes of odd degree. $\endgroup$
    – user317176
    Oct 17, 2023 at 23:48

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .