2
$\begingroup$

Since path cannot have repeated vertices, the definition for

A graph which exactly two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component

seems to must refer to Euler trail. Is Euler path sth else and if it is? (I think it can just be a path graph.)

Another question is,

An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component

this is from Wikipedia, How can a graph with zero odd-degree vertices has an Eulerian trail?

$\endgroup$

2 Answers 2

1
$\begingroup$

As OP notes, a path cannot have repeated vertices, but a trail can [path, Wikipedia][1]. This forms the distinction between an Eulerian path (no repeated vertices) and an Eulerian trail (possibly repeated vertices).

As for the second question: An Eulerian trail can end at the same vertex as it starts at, which would be the case if all vertex degrees are even.

[1]: https://en.wikipedia.org/wiki/Path_(graph_theory)#:~:text=A%20trail%20is%20a%20walk,also%20all%20edges)%20are%20distinct.

$\endgroup$
0
$\begingroup$

To answer your first question, firstly the convention is "Eulerian path" and "Eulerian trail". Secondly, here are the definitions of the 2 phrases, copied directly from Google.

Eulerian path: "a path that goes through every edge of a graph exactly once"

Eulerian trail: "a trail in a finite graph that visits every edge exactly once"

An Eulerian path and Eulerian trail are basically the same thing. They visit each edge exactly once with repeats of vertices allowed. Paths can have repeated vertices. I might also add that an Eulerian cycle or circuit are basically the same things, just that they must end at the vertex that they started on.

To answer your second question, there are many proofs online, but a simple proof of existence is that suppose you have a graph with $n$ vertices and exactly $2$ odd-degree vertices. This graph has an Eulerian path. Let the $2$ odd-degree vertices be called $a$ and $b$. We add another vertex $x$ connected only to $a$ and $b$. Then, we get a graph with $n+1$ vertices and exactly $0$ odd-degree vertices. Since the previous graph has an Eulerian trail, our new graph also has an Eulerian trail.

$\endgroup$
1
  • $\begingroup$ Sorry to OP and thanks to you for pointing out the error. $\endgroup$ Commented Dec 17, 2023 at 14:56

You must log in to answer this question.

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