Hamilton path and circuit rounded path problem

  • #1
98
3

Summary:

If it is not helpful to us to know if degree odd or even, how can we think in rounded paths?

Main Question or Discussion Point

1590128075856.png

Here is a graph. I wonder if it has hamilton path or circuit. In hamilton path we have to cross once and only once at an edge, and the start and the finish must be different locations. In hamilton circuit we have to start and finish the same edge. So the circle which B is rounded, which kind of case in there?
 

Answers and Replies

  • #2
34,387
10,475
You can't visit a vertex more than once (unless you start and finish there after visiting all others, for a cycle), so the loop at B is useless, it can't be used.
 
  • #3
75
44
It has a Hamilton path, but not a Hamilton circuit.
Your definitions of both above are incorrect. A Hamilton path/circuit says every vertex (not connection) must be visited once.
I was also able to traverse the above graph visiting every path once, but it again wasn't a circuit, which is only possible if every vertex has an even number of connections. I don't know the name of that sort of path.
 
  • #4
34,387
10,475
Ah, I missed that OP misunderstood the definition.

A path that takes every edge once is an Euler path (or Euler tour, if closed). A loop doesn't make a difference, as long as it is connected to the rest of the graph.
 
  • #5
98
3
It has a Hamilton path, but not a Hamilton circuit.
Your definitions of both above are incorrect. A Hamilton path/circuit says every vertex (not connection) must be visited once.
I was also able to traverse the above graph visiting every path once, but it again wasn't a circuit, which is only possible if every vertex has an even number of connections. I don't know the name of that sort of path.
Can we say that the hamilton path is E-B-A-D-C ? And which are my thoughts wrong? the definition or summary?
 
  • #6
75
44
Can we say that the hamilton path is E-B-A-D-C ?
That is one Hamiltonian path, yes.

And which are my thoughts wrong? the definition or summary?
Both definition and summary seem to speak of Euler paths. Degree of vertices matters for a Euler path, but not for Hamiltonian. Euler paths try to visit the edges, while Hamiltonian paths visit the vertices. Your solution EBADC is a Hamiltonian path, but it doesn't meet any of the definitions of the OP. Some of the vertices have odd degree, and the OP speaks of crossing each edge once and only once, yet your path EBADC misses a lot of them.

Yes, your graph does have a Euler path as well, but not a Euler circuit due to some of the vertices having odd degree.
 
  • Like
Likes requied
  • #7
98
3
Thank you for attention Halc.
1590263950522.png

In addition, I couldn't find the euler path in the graph of figure (a). Is there still an euler path if none the degree of vertices is odd or we must find these by trying one by one?
And would you like to control whether my other answers are true? I really appreciate it.
 
  • #8
34,387
10,475
Looks right.

For (a), every Euler circuit is also an Euler path.
 
  • Informative
Likes requied
  • #9
75
44
In addition, I couldn't find the euler path in the graph of figure (a). Is there still an euler path if none the degree of vertices is odd or we must find these by trying one by one?
I've seen at least one definition that says that a Euler path must start and end on different verticies, in which case no graph can be both a Euler path and a Euler circuit. Other definitions don't have the vertex restriction, thus any Euler circuit is also a valid Euler path. I think your text above uses the latter less restrictive definition.
And would you like to control whether my other answers are true? I really appreciate it.
All looks fine, including the yellow '?'.
 
  • #10
98
3
every Euler circuit is also an Euler path.
at least one definition that says that a Euler path must start and end on different verticies, in which case no graph can be both a Euler path and a Euler circuit
I think there is a little oppositeness here :)
I think your text above uses the latter less restrictive definition.
So can't we actually know which one we need to use? Or the latest definitions be accepted at mathematics?
 
  • #11
75
44
I think there is a little oppositeness here :)
Oh definitely.

So can't we actually know which one we need to use? Or the latest definitions be accepted at mathematics?
Yea, you use the rules as quoted by the text you're using.

The OP says "we have to cross once and only once at an edge, and the start and the finish must be different locations ", but of course that's not a direct quote from whatever text since he equates "Hamilton path" to that rule.
I googled "Euler path" and the top hit, the one with the summary that comes up, says "An Euler path starts and ends at different vertices" (jlmartin.faculty.ku.edu). I think the OP is using that exact site since his graph comes up very first thing if you click on that link. But wiki mentions no such rule, and I suspect neither did Euler, from whom the definition comes. No other hit on the google search expresses the 'must start and end at different vertices' rule. So why does that one rebel definition manage to propagate to the top of the google search?

The site goes on to make this statement:
JLMartin said:
The inescapable conclusion (“based on reason alone!”): If a graph G has an Euler path, then it must have exactly two odd vertices.
All the other sites prove that a graph has a Euler path iff it has at most two odd vertices.

So I agree with you. A Euler path can start and end anywhere it likes, which makes sense given the basic concept of a path. Figure A has a Euler path. The google search unfortunately hits the jlmartin site which is one of the few rebel ones.
 

Related Threads on Hamilton path and circuit rounded path problem

  • Last Post
Replies
2
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
10
Views
6K
  • Last Post
Replies
3
Views
3K
Replies
1
Views
3K
Replies
1
Views
3K
Replies
2
Views
1K
  • Last Post
Replies
5
Views
506
  • Last Post
Replies
5
Views
2K
Top