Talk:Ore's theorem

A flaw in the proof of Ore's theorem

Hello,

Citing the current proof:

Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v₁v₂...v_n, for otherwise it would be possible to add edges to G without breaching property (*).

So you would construct a G2 graph from G by adding an edge to G's edges. For sure it would not break the property about the degrees. But you have no guarantee that G2 is still non-hamiltonian when you add this edge. By construct, the G graph was the graph with maximum number of edges among all other non-hamiltonian graphs with n vertices:

let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*).

This means that you cannot point out the contradiction that this was supposed to be the biggest graph of its kind, and you were able to construct an even bigger graph of the same kind.

There is a way to rewrite this that solves the problem. The trick is to define G as a non-hamiltonian graph that is "nearly hamiltonian", in the sense that adding a single edge e makes it hamiltonian. And then the whole thing works, provided that the rest of the proof is adapted a bit.

I know this is probably what was meant here. But it's not what is written.

Also, I did a schema for the French Wikipedia, for the proof of Dirac's theorem, that applies as well for the proof of Ore's theorem, since it's almost the same proof. Its name is "Dirac theorem.svg" and it might be useful to illustrate this article.

Best, --MathsPoetry (talk) 17:34, 3 January 2013 (UTC)

I don't think any changes or tricks are needed. If a graph has no Hamiltonian path, then it takes at least two new edges to create a Hamiltonian cycle. For, when an edge is added that creates a Hamiltonian cycle, the endpoints of that edge must already have been connected by a Hamiltonian path. So, if you add edges one by one, you will always get to a state that has a Hamiltonian path but no cycle, before getting to a state that has a Hamiltonian cycle. —David Eppstein (talk) 01:57, 4 January 2013 (UTC)

Hi David and happy new year.

What you say here is true, but it does not relate to the current demonstration in the article.

You don't define G as a graph verifying (*) that is biggest in the sense that it is not hamiltonian and that it becomes hamiltonian when adding a single edge. You define it as the graph, among all non-hamiltonian graphs verifying (*), that has the most edges. That's not the same thing.

Of course, you can prove that both concepts are equivalent, but that's unnecessary work.

And, "Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path" is not straightforward at all with G defined the way it is currently.

Best --MathsPoetry (talk) 08:36, 4 January 2013 (UTC)

If a graph had no Hamiltonian path then (by the above fact about adding two edges) adding any single edge would still leave a graph with no Hamiltonian cycle, so it couldn't be maximal. It really is straightforward. —David Eppstein (talk) 16:57, 4 January 2013 (UTC)

If you are writing for non-specialists, I strongly doubt they are able to understand such reasoning without detailed steps and explanations, and I doubt even more that they are able to do it by themselves if you don't give anything. If you are writing for specialists, this demonstration is useless all the same, because they know it already. --MathsPoetry (talk) 20:05, 4 January 2013 (UTC)

I think the more confusing aspect of the proof was the use of two nested levels of proof by contradiction, which requires non-specialists to keep track of what is being assumed and how a contradiction implies the falsity of the assumption. I've rewritten it to avoid that issue, and I hope clarify your confusion as well. —David Eppstein (talk) 21:57, 4 January 2013 (UTC)

" let H be formed from G by adding edges one at a time that do not create a Hamiltonian cycle, until no more edges can be added" : it's exactly what I was proposing

Thanks David, I think it is way clearer like this. --MathsPoetry (talk) 07:53, 5 January 2013 (UTC)

Hey, there is something else that is great about the new formulation! It is that you avoid the semi-magical invocation of the pigeonhole principle. It was also disturbing me, because it required some extra work to apply the pigeonhole principle.

And you are right, the two nested levels of proof by contradiction was also bad, although it was not really my point (my point was that the second contradiction was not expressed correctly). Anyway, the new, more direct approach is way better from a didactic point of view.

By the way, the usual proof of Dirac's theorem has the same problem of nested contradictions that you pointed out...

I'll translate your new proof to the French Wikipedia, it will be much shorter than what I have got to. I'll give you the credits, of course.

Unrelated: is the proof of Ore's theorem on ProofWiki yours? It looks identical to the previous version of this proof. Or maybe they just copied your work? --MathsPoetry (talk) 08:22, 5 January 2013 (UTC)

Thanks. Re the ProofWiki variant: I had nothing to do with that. I think the similarity can be ascribed to the fact that there are only so many ways to rearrange the same basic ideas. —David Eppstein (talk) 08:29, 5 January 2013 (UTC)

Indeed. One I find very elegant is the one from Godfried Toussaint [1].

It is also fascinating that Dirac, Ore, Posa, Bondy-Chvatal all use the same mechanism for constructing a cycle out of a path. I am wondering whether there is something very deep about this construct, or this is just a demonstration trick. --MathsPoetry (talk) 09:40, 5 January 2013 (UTC)

Directed graphs

Hi,

The article says that Woodall found a variant for directed graphs (1972). Isn't Meyniel's theorem (1973) also a variant on Ore's theorem for directed graphs ? --MathsPoetry (talk) 09:46, 5 January 2013 (UTC)

Yes, looks like. Is the statement of the theorem in Hamiltonian path accurate? I mistrust the use of "some" as a quantifier. —David Eppstein (talk) 16:07, 5 January 2013 (UTC)

I don't think so. I found this: "Meyniel's theorem states that a strict diconnected digraph has a directed Hamilton cycle if d(u) + d(v) ⩾ 2n − 1 for every pair u, v of nonadjacent vertices." in Science Direct

Speaking about mistakes in Hamiltonian path: I think the date for Bondy and Chvátal theorem is 1976, not 1972.

Best, --MathsPoetry (talk) 17:23, 5 January 2013 (UTC)

Possible error in algorithm

The algorithm currently states "Reverse the part of the cycle between $v_{i+1}$ and $v_{j}$ (inclusive)."

I think it should say:

If $i>j$ reverse the part of the cycle between $v_{i+1}$ and $v_{j}$ (inclusive), and if $j>i$ reverse the part of the cycle between $v_{j+1}$ and $v_{i}$ (inclusive).

I determined this only through doing my own worked examples, and I'm not an expert on graph theory. Can someone who knows more about this than me please check?

Mauxb (talk) 10:40, 4 December 2018 (UTC)

I take it back. I now understand the part of the cycle that needs to be reversed is the clockwise portion between $v_{i+1}$ and $v_{j}$ (inclusive), looping around the cycle if necessary (assuming the points are labelled so that the index increases clockwise). I wonder if there is some way to make this clearer in the original. Perhaps and illustrated example?

Mauxb (talk) 12:45, 5 December 2018 (UTC)