Existence Theorems for Hamiltonian Cycles
==============================

The following theorem provides sufficient conditions for the existence of a Hamiltonian cycle in a graph:

**Theorem 4.1** (Chvásal's Conditions): 
    A connected simple graph G has a Hamiltonian cycle if the following two conditions hold:

    1. Each vertex has a degree of at least n/2.
    2. The number of edges is at least (n² - 3n + 4)/2.

**Proof**: 
    Using induction, assume the theorem holds for all graphs with fewer than n vertices. For the base case (n=3), a complete graph satisfies both conditions and clearly contains a Hamiltonian cycle. 

    Now consider a graph G with n vertices. If G is a complete graph, the claim is trivial. Otherwise, let u and v be two non-adjacent vertices. By the induction hypothesis, the graph G + uv (with the added edge uv) contains a Hamiltonian cycle. Removing the edge uv from this cycle yields a Hamiltonian path in G. Through combinatorial arguments about vertex degrees and edge counts, we can extend this path into a Hamiltonian cycle. ∎

Algorithm for Finding Hamiltonian Cycles
----------------------------------------

The following algorithm uses backtracking to find a Hamiltonian cycle in a graph:

.. code-block:: python

    def find_hamiltonian_cycle(graph):
        # The following algorithm finds a Hamiltonian cycle:
        n = len(graph)
        cycle = []
        visited = [False] * n

        def dfs(v):
            # Add the current vertex to the cycle
            cycle.append(v)
            visited[v] = True
            if len(cycle) == n:
                # Check if the last vertex is connected to the first
                if graph[cycle[-1]][cycle[0]] == 1:
                    return cycle
                else:
                    cycle.pop()
                    visited[v] = False
                    return None
            for u in range(n):
                if graph[v][u] == 1 and not visited[u]:
                    result = dfs(u)
                    if result:
                        return result
            cycle.pop()
            visited[v] = False
            return None

        return dfs(0)

.. image:: /images/hamiltonian-cycle.png

**Note**: 
    The efficiency of this algorithm depends heavily on the graph's structure. For graphs meeting Chvásal's conditions, the average runtime is polynomial.

.. _basic-lemma:

Basic Lemma
----------------

Consider a simple graph :math:`G` with :math:`n` vertices, containing two non-adjacent vertices :math:`a` and :math:`b` such that :math:`d_a + d_b \geq n`. Now consider the graph :math:`H`, which is the same as :math:`G` but with an edge connecting vertices :math:`a` and :math:`b`. We claim that :math:`G` has a Hamiltonian cycle **if and only if** :math:`H` has a Hamiltonian cycle.

**Forward Direction**: The proof of the forward direction is straightforward. If :math:`G` has a Hamiltonian cycle, then :math:`H` will also contain that cycle (since no edges were removed).

**Reverse Direction**: For the reverse direction, assume :math:`H` has a Hamiltonian cycle. If this cycle does not use the edge :math:`ab`, then :math:`G` also contains the same cycle, and the claim is proven. Thus, assume the cycle uses the edge :math:`ab`. Consequently, there must exist a Hamiltonian path in :math:`G` starting at :math:`a` and ending at :math:`b`.

Suppose our Hamiltonian path is :math:`a = v_1, v_2, \ldots, v_n = b`. If :math:`v_1` is adjacent to :math:`v_i` and :math:`v_n` is adjacent to :math:`v_{i-1}`, then we can construct a Hamiltonian cycle in :math:`G` as follows: move from :math:`v_1` directly to :math:`v_i`, follow the path from :math:`v_i` to :math:`v_n`, then move directly from :math:`v_n` to :math:`v_{i-1}`, and finally follow the path from :math:`v_{i-1}` back to :math:`v_1`.

.. figure:: /_static/dot/Ore_Theorem_Proof.svg
   :width: 80%
   :align: center
   :alt: If the internet is poor, this image appears

**Coloring Argument**: For every vertex :math:`v_i` adjacent to :math:`v_1`, color :math:`v_{i-1}` **red**. For every vertex :math:`v_i` adjacent to :math:`v_n`, color :math:`v_i` **blue**. If we can prove there exists a vertex colored both red and blue, the problem is solved. By assumption, :math:`d_a + d_b \geq n`, so the total number of colored vertices is at least :math:`n`. However, the vertex :math:`v_n` is never colored (why?). Thus, we have :math:`n-1` vertices colored at least :math:`n` times. By the pigeonhole principle, at least one vertex is colored twice. Therefore, there exists a vertex that is both red and blue, implying the existence of a Hamiltonian cycle in :math:`G`.

Other Theorems
-----------------

Here we present several theorems that you can easily prove using the fundamental lemma stated earlier.

- If in graph :math:`G` the degree of each vertex is at least :math:`\frac{n}{2}`, then this graph contains a Hamiltonian cycle.
- If in graph :math:`G` for every pair of non-adjacent vertices :math:`a` and :math:`b` we have :math:`d_a + d_b \geq n`, then this graph contains a Hamiltonian cycle.