text: Ore's theorem
  
  Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.
  
  Formal statement
  
  Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if
  
  deg v + deg wn for every pair of distinct non-adjacent vertices v and w of G (*)
  
  then G is Hamiltonian.
  
  Proof
  
  It is equivalent to show that every non-Hamiltonian graph G does not obey condition (*). Accordingly, let G be a graph on n ≥ 3 vertices that is not Hamiltonian, and 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. Let x and y be any two non-adjacent vertices in H. Then adding edge xy to H would create at least one new Hamiltonian cycle, and the edges other than xy in such a cycle must form a Hamiltonian path v1v2...vn in H with x = v1 and y = vn. For each index i in the range 2 ≤ in, consider the two possible edges in H from v1 to vi and from vi − 1 to vn. At most one of these two edges can be present in H, for otherwise the cycle v1v2...vi − 1vnvn − 1...vi would be a Hamiltonian cycle. Thus, the total number of edges incident to either v1 or vn is at most equal to the number of choices of i, which is n − 1. Therefore, H does not obey property (*), which requires that this total number of edges (deg v1 + deg vn) be greater than or equal to n. Since the vertex degrees in G are at most equal to the degrees in H, it follows that G also does not obey property (*).
  
  Algorithm
  
  Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
  
  1. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
  2. While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:
  • Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges from vi to vj and from vj + 1 to vi + 1
  • Reverse the part of the cycle between vi + 1 and vj (inclusive).
  
  Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices vi and vi + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.
  
  Related results
  
  Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.
  
  In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence.
  
  Woodall (1972) found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is an edge from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges. A closely related theorem by Meyniel (1973) states that an n-vertex strongly connected digraph with the property that, for every two nonadjacent vertices u and v, the total number of edges incident to u or v is at least 2n − 1 must be Hamiltonian.
  
  Ore's theorem may also be strengthened to give a stronger condition than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic (Bondy 1971).
explanation: The document provides a detailed explanation of Ore's theorem in graph theory, including its formal statement, proof, algorithm for constructing a Hamiltonian cycle, and related results. It does not contain a specific question or a question and answer.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: Ore's theorem
  
  Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.
  
  Formal statement
  
  Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if
  
  deg v + deg wn for every pair of distinct non-adjacent vertices v and w of G (*)
  
  then G is Hamiltonian.
  
  Proof
  
  It is equivalent to show that every non-Hamiltonian graph G does not obey condition (*). Accordingly, let G be a graph on n ≥ 3 vertices that is not Hamiltonian, and 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. Let x and y be any two non-adjacent vertices in H. Then adding edge xy to H would create at least one new Hamiltonian cycle, and the edges other than xy in such a cycle must form a Hamiltonian path v1v2...vn in H with x = v1 and y = vn. For each index i in the range 2 ≤ in, consider the two possible edges in H from v1 to vi and from vi − 1 to vn. At most one of these two edges can be present in H, for otherwise the cycle v1v2...vi − 1vnvn − 1...vi would be a Hamiltonian cycle. Thus, the total number of edges incident to either v1 or vn is at most equal to the number of choices of i, which is n − 1. Therefore, H does not obey property (*), which requires that this total number of edges (deg v1 + deg vn) be greater than or equal to n. Since the vertex degrees in G are at most equal to the degrees in H, it follows that G also does not obey property (*).
  
  Algorithm
  
  Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
  
  1. Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
  2. While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:
  • Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges from vi to vj and from vj + 1 to vi + 1
  • Reverse the part of the cycle between vi + 1 and vj (inclusive).
  
  Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices vi and vi + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.
  
  Related results
  
  Ore's theorem is a generalization of Dirac's theorem that, when each vertex has degree at least n/2, the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least n.
  
  In turn Ore's theorem is generalized by the Bondy–Chvátal theorem. One may define a closure operation on a graph in which, whenever two nonadjacent vertices have degrees adding to at least n, one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph. The Bondy–Chvátal theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian; since the complete graph is Hamiltonian, Ore's theorem is an immediate consequence.
  
  Woodall (1972) found a version of Ore's theorem that applies to directed graphs. Suppose a digraph G has the property that, for every two vertices u and v, either there is an edge from u to v or the outdegree of u plus the indegree of v equals or exceeds the number of vertices in G. Then, according to Woodall's theorem, G contains a directed Hamiltonian cycle. Ore's theorem may be obtained from Woodall by replacing every edge in a given undirected graph by a pair of directed edges. A closely related theorem by Meyniel (1973) states that an n-vertex strongly connected digraph with the property that, for every two nonadjacent vertices u and v, the total number of edges incident to u or v is at least 2n − 1 must be Hamiltonian.
  
  Ore's theorem may also be strengthened to give a stronger condition than Hamiltonicity as a consequence of the degree condition in the theorem. Specifically, every graph satisfying the conditions of Ore's theorem is either a regular complete bipartite graph or is pancyclic (Bondy 1971).
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document provides a detailed explanation of Ore's theorem in graph theory, including its formal statement, proof, algorithm for constructing a Hamiltonian cycle, and related results. It does not contain a specific question or a question and answer.
  
  Label: no-question