State Dirac’s and Ore’s Theorem in graph theory
Answers
Formal statement[edit]
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 distinct non-adjacent vertices v and w of G (*)then G is Hamiltonian.
Proof[edit]Let v and u be any two vertices in G. We will be finished if we can show that there is a Hamiltonian path from v to u. Form a new graph G* by adding a new vertex w to G with w adjacent to precisely v and u. Then in G* , every two non-adjacent vertices x, y in G satisfy, deg(G*) x + deg(G*) y ≥ n + 1 = |V(G* )| , and so all the edges between vertices of G belong to the closure of G* . But after these edges are added to the closure of G* , we see that for any vertex x in G, deg(G*) x + deg(G*) w = (n − 1) + 2 = n + 1 , and so all edges from w to the vertices of G are also included in the closure of G* . Thus the closure of G* is complete and it follows that G* must have a Hamiltonian cycle, call it C. But since w is of degree 2, both of the edges xv and xu are in C. So it follows that C - w is a Hamiltonian path from v to u and the result follows.
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 ≤ i ≤ n, 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[edit]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 + 1Reverse 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.
i don't know about dirac's theorem
sorry