1
$\begingroup$

I was going through graph theory and came across the term Euler path or some people prefer Euler trail as vertices can repeat.

According to the definition from wiki (https://en.wikipedia.org/wiki/Eulerian_path), Euler path is defined as under

In graph theory, a Eulerian trail (or Eulerian path) is a trail in a graph which visits every edge exactly once.

Following are the conditions for Euler path,

An undirected graph (G) has a Eulerian path if and only if every vertex has even degree except 2 vertices which will have odd degree, and all of its vertices with nonzero degree belong to a single connected component.

So as per the definition, I need to cover all edges in a connected graph with non zero degrees.

The same information is stated here at geeks for geeks(https://www.geeksforgeeks.org/eulerian-path-and-circuit/).

so if I need to only consider vertices with non zero degrees then graph (G)can be disconnected?

Note: These are the other information I collected from the wiki page

1)Finite connected graph (with vertices of even degree except 2 or 0 with the odd degree) will have a Euler path. 2)But Euler path can also be present in the disconnected graph as shown in the following picture

enter image description here

3) Doubt does following graph have Euler path,

My answer ,No as all vertices are not in same connected component.

enter image description here

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Try working through some examples. Enumerate all graphs with 2 or 3 vertices. You should be able to work out the answer on your own. $\endgroup$ – D.W.♦ Jun 10 '18 at 17:28
  • $\begingroup$ Actually it seems this is already answered on the Wikipedia article you listed: see the sentence beginning "For finite connected graphs...", and then tell us what inferences you can draw from that fact... I'm not sure there's much point in us repeating material already available elsewhere, so if the answer can be inferred by reading the Wikipedia article, I encourage you to spend more time on research before asking in the future. $\endgroup$ – D.W.♦ Jun 10 '18 at 17:28
  • $\begingroup$ @D.WI did, geeksforgeeks.org/eulerian-path-and-circuit look at 2 conditions they listed there for a path to be Euler path, they said "All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges)." $\endgroup$ – Thinker Jun 10 '18 at 18:52
  • $\begingroup$ @D.W. still, I am again going through wiki in case I missed something thanx for pointing out. $\endgroup$ – Thinker Jun 10 '18 at 19:08
  • $\begingroup$ Well, reading some other site may well be useful, too, but it's not a replacement for reading and thinking about that one sentence I pointed you to. But that sentence you quoted is also good -- think about the implications of that, too. I suggest you try to think of the smallest graph you can think of where you're not sure whether it counts as having an Euler path, try to apply the definition to it, and if you're still confused, show that graph in the question and tell us why you're unsure about how the definition applies. $\endgroup$ – D.W.♦ Jun 10 '18 at 19:13
4
$\begingroup$

It really comes down to your definition of an Euler trail. The one I'm familiar with is similar to the one on Wikipedia:

An Euler trail is a trail (path that allows repeats) that uses every edge exactly once.

With this definition, an Euler trail doesn't have to touch every vertex: if there's a vertex with no edges, the Euler trail doesn't have to go anywhere near it.

However, if there's a vertex with positive degree, and another vertex with positive degree, and they're not (weakly) connected, then there can be no Euler trail. Because if you use the edges on one, there's no way to reach the edges on the other.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.