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.
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 w ≥ n for every pair of non-adjacent vertices v and w of G (*)
then G is Hamiltonian.
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 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 (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v1v2...vn, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v1 cannot be adjacent to vn, for otherwise v1v2...vn would be a Hamiltonian cycle. By property (*), deg v1 + deg vn ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, vi is adjacent to v1 and vi − 1 is adjacent to vn. But the cycle v1v2...vi − 1vnvn − 1...vi is then a Hamilton cycle. This contradiction yields the result.
Palmer (1997) 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:
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.
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 w ≥ n for every pair of non-adjacent vertices v and w of G (*)
then G is Hamiltonian.
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 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 (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v1v2...vn, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v1 cannot be adjacent to vn, for otherwise v1v2...vn would be a Hamiltonian cycle. By property (*), deg v1 + deg vn ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, vi is adjacent to v1 and vi − 1 is adjacent to vn. But the cycle v1v2...vi − 1vnvn − 1...vi is then a Hamilton cycle. This contradiction yields the result.
Algorithm
Palmer (1997) 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 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.
0 comments:
Post a Comment
Let us know your responses and feedback