Talk:Hamiltonian Path

It would be nice if you included an np-completeness proof for finding a hamilton path. I also think that maybe it would be best to pick a different main image. You could make one that showed more clearly what a hamilton path is and that looked more intriguing.

Nordhr 17:20 29 June 2011

I am wondering if the proof sections are too difficult. Maybe I should make them easier somehow, or maybe hide them. Let me know. NP-completeness proof is hard to find. Jorin 09:22, 18 May 2012 (EDT)

For those of you on my feedback team looking at this, please let me know how the new visuals are. I am worried that the animation in the proof could me more helpful or contain more information. Thanks! Jorin 09:43, 31 May 2012 (EDT)

I think the new visuals look pretty good. For the animation in the proof of Dirac's Theorem, personally I feel it might be helpful if you make it more clear what the order of the process is. It might be a little bit confusing at first because the animation is non-stop. Maybe you can add a frame giving a "start" message, or add numbers in the lower-right corner of the images to indicate the order? Chengying

Well done on the edits! The proofs, especially, are much better now -- engaging, clear, and complete. Most of the suggestions I have for you now are relatively minor in terms of how much change they entail, but they're still important:

• In the basic description, you say, "If a walk begins and ends at the same vertex, it's called a cycle." But this is true for paths, not walks (or at least, not all walks).
• In your initial statement of Dirac's theorem, you need to say what m is.
• In the second paragraph of your proof for Dirac's theorem, I keep reading "For more helpful terms and concepts..." to mean, "For terms and concepts that are more helpful than these..." So I would suggest replacing "more" with "other."
• In the fourth paragraph of your proof for Dirac's theorem, I suggest combining the ideas in the two sentences, "...we can create a Hamiltonian path in G, but we do not have that one last edge to connect the path and make it a Hamiltonian cycle. If any new edge were to be added to G, then the new graph would be a Hamiltonian graph! " so that it's absolutely clear that "maximal non-Hamiltonian graph" requires that adding any edge between two non-adjacent vertices makes the graph Hamiltonian. Right now, that definition is not apparent to the reader.
• In the fifth paragraph of this proof, you say, "we can make a cycle in G + uv that begins at u and ends at v." However, a cycle, by definition, begins and ends on the same vertex. I understand what you mean here, but you should find some other way to express this so that it's mathematically accurate. In the next sentence, you refer to it as a "path" instead, which is more accurate, though I think talking about it as a cycle is valuable, too. What I'm saying is, try to clean up this paragraph so that it's clear that you're talking about a path in G, starting on u and ending on v, such that adding the edge uv makes this path in G into a cycle in G + uv.
• Right below where you state the implication of "v \notin S\cup T...." you have, "The vertex v is not in G because it is a simple graph." This is incorrect -- I think you meant to say, "The vertex v is not in T because G is a simple graph." ?
• As you go into the conclusion of this proof, instead of saying, "...because if
$d(u)>\frac{n}{2}\Rightarrow d(v)<\frac{n}{2}$
And vice versa," you should say, "...because [omit "if"]
$d(u)>\frac{n}{2}\Leftrightarrow d(v)<\frac{n}{2}$
[omit "And vice versa."]
• In "An Example," instead of referring to "this graph," put "Image 1," or whatever number's appropriate, in the caption of the graph and refer to it by that label. It will be much clearer that way.
• In your bullet points in the proof based on the specific example, you use "cycle" where it should be "path."
• In the seventh paragraph of that same proof-example, you say, "Furthermore, adding the number of total elements in both sets is the same as and the number of elements that the two sets have together plus the ones they have in common," which makes no sense. Not sure what you meant there -- possibly "add" instead of "and"?
• When you state the Bondy-Chvatal theorem, you need to specify what n is.
• At the end of the first paragraph under "Which Theorem is Better?" you say, "For example, consider the graph with..." but never really explain what you'd like us to consider and why exactly it shows one theorem is stronger than the other. You just need one more sentence here stating what you want us to notice.
• In the third paragraph under "Alternate Statements for the Bondy-Chvatal Theorem," you state that, "Complete graphs with more than three vertices are definitely Hamiltonian, since any necessary edge to complete the cycle is always present." In fact, this is true for all complete graphs on three or more vertices.
• There's something odd going on in the second sentence of the second paragraph of "Why It's Interesting." What did you mean to say here?

Diana 15:21, 13 June 2012 (EDT)

Gene 7/10

a Hamiltonian path is a series of vertices edges

vertices edges? Huh??

A trip around the graph is called a walk

SUCH a trip ... -- if you don't go from vx to vx, ain't a walk.

A Hamiltonian Path in boldface is a path in a graph that will visit [visits] all the vertices exactly once.

Derived from Hamiltonian paths are Hamiltonian cycles.

"First" and "last" need to be clarified in this paragraph. What are they?

Derived from Hamiltonian paths are Hamiltonian cycles.

what do you mean "derived"?

There is no specific characterization of a Hamiltonian graph

Huh?

Looking good! A few minor things:

• I put two of the comments above in bold (I think Gene left those comments?), because they're important, and it doesn't look like you've implemented them yet.
• I made a few really minor edits directly to your page. You can see them by checking the history.
• First paragraph of the basic desc. is very choppy; can you start some of those sentences with connecting words and other forms of liaison instead of "A trip ... A walk ... A Hamiltonian Path..."?
• Second sentence, second paragraph of basic desc. should be: "A cycle in general is a path where the first and last vertices are the same."
• Last sentence of the basic desc., try, "The More Mathematical Explanation lays out some theorems to determine whether a graph is Hamiltonian."
• In the fourth paragraph of the first proof, this sentence: "Let u and v be two non-adjacent vertices in G, and to make a Hamiltonian cycle, we add the new edge uv" is confusing. Try: "Let u and v be two non-adjacent vertices in G such that adding the new edge uv creates a Hamiltonian cycle in G."
• At the end of that same paragraph, use "double edges" instead of "unnecessary edges."
• In the fifth paragraph, I think you mean to say, "...we can also define a Hamiltonian path in G that begins at..." Even if that isn't what you meant to say, it would make the next paragraph much clearer, so I strongly suggest it.
• In the sixth paragraph, put "not G + uv" in parentheses.
• In the 11th-ish paragraph (hard to tell this far down...), it would be better to say, "Thus v meets neither definition of S or T, and so |ST| < n." Then start a new paragraph with "We also know that..."
• At the very end of that proof, "We have found non-Hamiltonian graphs where m ≤ n/2, which is the opposite of our assumption," isn't quite right. Our negation claimed that there existed some non-Hamiltonian graph where... (etc.), so just finding cases where this isn't true wouldn't be sufficient. That's fine, because that isn't what you did. You've shown that it's impossible for a non-Hamiltonian graph to have n ≥ 3 and mn/2.
• The first sentence of your statement of the Bondy-Chvatal Theorem is currently:
Let G be a simple graph and let u and v be nonadjacent vertices in G and n is the number of vertices such that d(u) + d(v)n.

This is confusing. I suggest:

Let G be a simple graph, and let n be the number of vertices in G. Let u and v be nonadjacent vertices in G such that d(u) + d(v)n.
• I feel like some words or some reasoning is missing from these sentences: "Therefore, we can determine whether or not a graph is Hamiltonian, depending on one condition. But Dirac's theorem is only and "if" statement. This means that this theorem only applies to graphs that meet the conditions." Can you clarify this? I know what you're getting at, but phrases like, "depending on one condition" and "the conditions" are too vague.
• In the third paragraph of the why it's interesting section, you say, "Since the graph is complete..." but you haven't established this, and it's not clear what "the graph" even refers to here, since it can't be G.
• In that same paragraph, you say, "Any path in the complete graph with a total weight of 0 will be a Hamiltonian path in G," but this isn't true. What about a path that just connects two of the vertices that are adjacent in G? This will have a weight of 0, but it's not a Hamiltonian path in G.

As far as I'm concerned, make these changes, and you're done! -Diana 10:31, 11 July 2012 (EDT)

Chris 12:14, 16 July 2012 (EDT)

Basic Description

• You title your page "Hamiltonian Path," then use "Hamiltonian Paths and Cycles" as a subtitle and use that same subtitle for the visual. This is potentially confusing to the reader.
• P2 The second paragraph can be tightened up. In fact, I think you need only one clear sentence about Hamiltonian cycles and it should go at the end of Paragraph 1.
• P3 Are theorems the only things laid out in the More Mathematical Explanation? What would the NP completeness proof be considered?

A More Mathematical Explanation

• Theorems: If there are many theorems, explain why you are choosing only two and why those particular two.
• Bondy-Chvatal Theorem
• An Example
• last sentence: Change "neither is G" to "so is G."

Why It's Interesting

• Knight's Tour: The animation is a Hamiltonian path, so it doesn't show that the graph is Hamiltonian.

Jorin 12:00, 18 July 2012 (EDT) Hey Chris,

Thanks for the suggestions! Just have some notes on what kind of edits I made. For the suggestions about the Basic Description, I took your thoughts into account, but I also had some ideas of my own. Since I discuss Hamiltonian cycles in the More Mathematical section in great detail, I did not want to discuss it in only one sentence at the end of P1. It felt like a different topic for me. So I got rid of P2, and then added a tighter description of Hamiltonian cycles to the beginning of P3. Also, the sentence about the theorems in the MME was meant as a segwey and I was hesitant to just mention NP-completeness without any kind of explanantion, but Diana said that it was ok to not explain it there, and so I put it.

Thanks! Jorin

Chris 13:15, 18 July 2012 (EDT)

In my opinion, you're almost there!

Basic Description

• P1, last sentence: Make terser: "A Hamiltonian path visits all the vertices exactly once."

I made a couple other minor edits; you can view them in the history if you like.

Theorems

• Did you choose the theorems because they are the most well-known or because they are the most useful?

The last section I think needs any work is "Which Theorem is Better?" I would change the title to "Comparing the Two Theorems." Also, I don't think the fact that the Dirac's Theorem proof contains more information is significant. Question: Are there ever situations in which Dirac's Theorem is more useful?