Ore's theorem
Encyclopedia
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 any two non-adjacent vertices
: if this sum is always at least equal to the total number of vertices in the graph, then the graph is Hamiltonian.
with vertices. We denote by the degree of a vertex in , i.e. the number of incident edges in to . Then, Ore's theorem states that if
then is Hamiltonian
.
, for otherwise it would be possible to add edges to without breaching property (*). Since is not Hamiltonian, cannot be adjacent to , for otherwise would be a Hamiltonian cycle. By property (*), , and the pigeon hole principle implies that for some in the range , is adjacent to v1 and is adjacent to . But the cycle is then a Hamilton cycle. This contradiction yields the result.
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.
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 , 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.
found a version of Ore's theorem that applies to directed graph
s. Suppose a digraph G has the property that, for every two vertices u and v, either there is a vertex 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.
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
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
proved in 1960 by Norwegian
Norway
Norway , officially the Kingdom of Norway, is a Nordic unitary constitutional monarchy whose territory comprises the western portion of the Scandinavian Peninsula, Jan Mayen, and the Arctic archipelago of Svalbard and Bouvet Island. Norway has a total area of and a population of about 4.9 million...
mathematician Øystein Ore
Øystein Ore
Øystein Ore was a Norwegian mathematician.-Life:Ore was graduated from the University of Oslo in 1922, with a Cand.Scient. degree in mathematics. In 1924, the University of Oslo awarded him the Ph.D. for a thesis titled Zur Theorie der algebraischen Körper, supervised by Thoralf Skolem...
. 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
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of any two non-adjacent vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
: if this sum is always at least equal to the total number of vertices in the graph, then the graph is Hamiltonian.
Formal statement
Let be a (finite and simple) graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with vertices. We denote by the degree of a vertex in , i.e. the number of incident edges in to . Then, Ore's theorem states that if
- for every pair of non-adjacent vertices and of (*)
then is Hamiltonian
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
.
Proof
Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all -vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, must contain a Hamiltonian pathHamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
, for otherwise it would be possible to add edges to without breaching property (*). Since is not Hamiltonian, cannot be adjacent to , for otherwise would be a Hamiltonian cycle. By property (*), , and the pigeon hole principle implies that for some in the range , is adjacent to v1 and is adjacent to . But the cycle is then a Hamilton cycle. This contradiction yields the result.
Algorithm
describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.- Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
- 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 + 1 and from vj 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 , the graph is Hamiltonian. For, if a graph meets Dirac's condition, then clearly each pair of vertices has degrees adding to at least .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 , one adds an edge connecting them; if a graph meets the conditions of Ore's theorem, its closure is a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
. 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.
found a version of Ore's theorem that applies to directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s. Suppose a digraph G has the property that, for every two vertices u and v, either there is a vertex 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.
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
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
or is pancyclic
Pancyclic graph
In the mathematical study of graph theory, a pancyclic graph is a directed or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph...
.