Let $G$ be a graph of degree $n\ge 3$ that satisfies the requirements of Ore's Theorem (my professor refers to it as "Ore's Condition"), to prove that $G+a$, $a$ an edge also satisfies Ore's Theorem. (That's the exact statement of the probem)

By $G+a$ it is to be understood "The graph $G$ with an added edge $a$."

For completeness I state Ore's theorem: Let $G$ be a connected graph of order $n\geq 3$. If for any pair of non-adjacent vertices $u$ and $v$ it is true that $$\deg{u}+\deg{v}\geq n,$$ then $G$ is Hamiltonian.

I am quite lost as to $\textit{what}$ exactly am I to prove. Am I to prove that $G+a$ is hamiltonian or that the logical implications of the theorem still stand? Any insight would be appreciated.

Also, can anyone sketch a proof (or throw a reference) of Ore's theorem's conditions on the degree of $v$ and $u$ being as strong as they get? That is, one could not relax the hypothesis?

Thanks to everyone in advance.


Probably your professor would like you to prove that if a graph satisfies the condition $det(u) + deg(v) \geq n$ then that same graph with an additional edge also satisfies that $deg(u) + deg(v) \geq n$. This is not hard, but probably the teacher was hoping that you would ask questions along the lines which you did.

Given a graph, $G$, if there are two vertices $u$ and $v$ such that $deg(u) + deg(v) \geq n$, then add the edge between them if it is not there already. Repeat this process until it stops and call this new graph the closure of $G$ and denote it $cl(G)$. Bondy-Chvatal proved that $G$ is Hamiltonian if and only if $cl(G)$ is Hamiltonian. The forward direction is trivial but the backwards direction is not. This is as strong as one can prove and it implies for instance Ore's theorem since the closure of a graph that satisfies the hyptheses of Ore's theorem is the complete graph. There are many theorems in this direction with different hypotheses some of which can be found at the wiki page I reference.


For a simple example of the sharpness of the theorem - the path of length 3 (i.e. the graph with vertices 1,2,3 and edges $(1,2)$ and $(2,3)$) is a graph which is as close as you can get to satisfying the Ore condition without actually meeting it. The only two non-adjacent vertices are 1 and 3, which have $\deg(1) + \deg(2) = 2 = 3-1$. But of course, it is not Hamiltonian.


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.