Fundamental Concepts in Graph Theory

This document elaborates on key graph theory concepts, including definitions, proofs, existence criteria, and methods for constructing specific graph structures such as Eulerian and Hamiltonian paths and cycles.

1. Basic Graph Terminology

• Node (Vertex): A fundamental entity in a graph, represented as a point or circle. We denote the set of nodes as $V$.

• Edge: A connection between two nodes. Edges can be:

  • Undirected: No sense of direction, connecting two nodes symmetrically.
  • Directed: Has a direction, indicating a one-way connection. A directed edge from $u$ to $v$ is written $(u,v)$, where $u$ is the tail and $v$ is the head.

• Graph: A mathematical structure consisting of a set of nodes $V$ and edges $E$ connecting pairs of nodes. Represented as $G=(V,E)$.

  • Undirected Graph: All edges are undirected.
  • Directed Graph (Digraph): All edges are directed.

• Degree:

  • Undirected Graphs: The degree of a node is the number of edges incident to it.
  • Directed Graphs: Nodes have:
    • In-degree: The number of incoming edges.
    • Out-degree: The number of outgoing edges.

2. Walks, Paths, and Cycles

• Walk: A sequence of nodes and edges, where each edge connects consecutive nodes in the sequence. Nodes and edges can be repeated.
• Path: A walk where no node is repeated (except possibly the start and end nodes).
• Cycle: A path that starts and ends at the same node, forming a closed loop.

3. Eulerian Walks, Paths, and Cycles

Definitions:

• Eulerian Walk: A walk that traverses every edge in the graph exactly once.
• Eulerian Path: An Eulerian walk that is a path (no node repetition, except possibly start and end).
• Eulerian Cycle: An Eulerian walk that is a cycle (starts and ends at the same node).

Existence Criteria:

Undirected Graphs:

1. Eulerian Cycle Existence Theorem:
   An undirected graph has an Eulerian cycle if and only if:

   • All nodes have an even degree.
   • The graph is connected (excluding isolated nodes).

2. Eulerian Path Existence Theorem:
   An undirected graph has an Eulerian path if and only if:

   • Exactly two nodes have odd degrees (the path must start at one odd-degree node and end at the other).
   • The graph is connected (excluding isolated nodes).

Directed Graphs:

1. Eulerian Cycle Existence Theorem:
   A directed graph has an Eulerian cycle if and only if:

   • Every node has equal in-degree and out-degree.
   • The graph is strongly connected (every node is reachable from any other node).

2. Eulerian Path Existence Theorem:
   A directed graph has an Eulerian path if and only if:

   • Exactly one node has $\text{out-degree}-\text{in-degree}=1$ (start of the path).
   • Exactly one node has $\text{in-degree}-\text{out-degree}=1$ (end of the path).
   • All other nodes have equal in-degree and out-degree.
   • The graph is connected (in a weaker sense: for the directed graph, the underlying undirected graph must be connected).

Proof Sketches:

Eulerian Cycle (Undirected Graph):

• If all nodes have even degree, every time we enter a node via an edge, we can leave it via another edge. This ensures that we can traverse all edges without being “trapped.”
• Connectivity ensures that all edges are reachable from any starting point.

Eulerian Path (Undirected Graph):

• For two nodes with odd degrees, the walk must start at one odd-degree node and end at the other. If more than two odd-degree nodes exist, it’s impossible to traverse all edges without breaking the degree condition.

Construction Algorithms for Eulerian Paths and Cycles

Here, we elaborate on two key algorithms used to construct Eulerian paths and cycles in undirected graphs: Fleury’s Algorithm and Hierholzer’s Algorithm.

1. Fleury’s Algorithm (Undirected Graphs)

Overview:
Fleury’s Algorithm systematically builds an Eulerian path or cycle by traversing edges while ensuring the graph remains connected after each traversal. It avoids using a “bridge” (an edge whose removal would disconnect the graph) unless there are no other options.

Steps:

1. Verify Eulerian Properties:
   Check whether the graph has an Eulerian path or cycle:

   • Eulerian cycle: All vertices have even degrees, and the graph is connected.
   • Eulerian path: Exactly two vertices have odd degrees, and the graph is connected.

2. Choose a Starting Vertex:

   • For an Eulerian cycle: Start at any vertex.
   • For an Eulerian path: Start at one of the two odd-degree vertices.

3. Traverse Edges Carefully:

   • At each step, choose an edge to traverse:
     • Prefer edges that are not “bridges” (edges whose removal would disconnect the remaining graph). To check if an edge is a bridge:
       1. Temporarily remove the edge from the graph.
       2. Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to check if all remaining vertices are still reachable.
       3. If the graph remains connected, the edge is not a bridge. Otherwise, it is a bridge.
     • If only bridges are available, use one.
   • Mark the traversed edge as used and move to the next vertex.

4. Repeat Until Complete:
   Continue traversing edges until all edges have been used exactly once.

5. Output the Path or Cycle:
   Record the sequence of edges traversed to form the Eulerian path or cycle.

Key Considerations:

• To check if an edge is a bridge, temporarily remove the edge and use a Depth-First Search (DFS) to see if the graph remains connected.
• The algorithm has a time complexity of $O(E^2)$ in its basic form due to repeated connectivity checks.

2. Hierholzer’s Algorithm (Undirected Graphs)

Overview:
Hierholzer’s Algorithm is more efficient than Fleury’s and constructs Eulerian cycles or paths by iteratively building and merging cycles. It avoids the need for connectivity checks during edge traversal.

Steps:

1. Verify Eulerian Properties:
   Ensure the graph satisfies the conditions for an Eulerian path or cycle:

   • Eulerian cycle: All vertices have even degrees, and the graph is connected.
   • Eulerian path: Exactly two vertices have odd degrees, and the graph is connected.

2. Choose a Starting Vertex:

   • For an Eulerian cycle: Start at any vertex.
   • For an Eulerian path: Start at one of the two odd-degree vertices.

3. Construct an Initial Cycle:
   Begin at the starting vertex and follow edges until returning to the starting vertex to form a closed cycle. Mark the edges used in this cycle.

4. Merge Cycles:

   • While unused edges remain, find a vertex on the current cycle that has unused edges.
   • Start a new cycle from this vertex, traversing unused edges until returning to the starting vertex of the new cycle.
   • Merge the new cycle into the current cycle by splicing the edge sequences together.

5. Repeat Until Complete:
   Continue merging cycles until all edges have been used.

6. Output the Path or Cycle:
   Record the sequence of edges to produce the final Eulerian path or cycle.

Efficiency:

• This algorithm efficiently constructs the path or cycle in $O(E)$ time, as it avoids the need for repeated connectivity checks by maintaining an adjacency list or edge list.

Comparison of Fleury’s and Hierholzer’s Algorithms

Example for Hierholzer’s Algorithm:
Let the graph have vertices $\{A,B,C,D\}$ and edges $\{(A,B),(B,C),(C,D),(D,A),(A,C)\}$.

1. Step 1: Start at vertex $A$.

   • Traverse $(A,B)\to (B,C)\to (C,D)\to (D,A)$ to form a cycle: $A\to B\to C\to D\to A$.

2. Step 2: Unused edge $(A,C)$ remains. Start a new cycle at $A$.

   • Traverse $(A,C)\to (C,A)$ to form a new cycle: $A\to C\to A$.

3. Step 3: Merge the cycles.

   • Original cycle: $A\to B\to C\to D\to A$.
   • New cycle: $A\to C\to A$.
   • Merged cycle: $A\to B\to C\to D\to A\to C\to A$ (Eulerian cycle).

4. Hamiltonian Walks, Paths, and Cycles

Definitions:

• Hamiltonian Walk: A walk that visits every node exactly once.
• Hamiltonian Path: A Hamiltonian walk that is a path.
• Hamiltonian Cycle: A Hamiltonian walk that is a cycle (also called a Hamiltonian circuit).

Existence Criteria:

Unlike Eulerian paths and cycles, there is no straightforward characterization for Hamiltonian cycles or paths. However, there are sufficient conditions and related theorems:

1. Dirac’s Theorem:
   If an undirected graph with $n\ge 3$ vertices satisfies $\mathrm{deg}(v)\ge n/2$ for every vertex $v$, then the graph contains a Hamiltonian cycle.

2. Ore’s Theorem:
   If an undirected graph satisfies $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$ for every pair of non-adjacent vertices $u$ and $v$, then the graph contains a Hamiltonian cycle.

3. Bondy–Chvátal Theorem:
   A graph is Hamiltonian if and only if its closure is Hamiltonian. The closure of a graph is formed by iteratively adding edges between non-adjacent vertices whose degree sum is at least $n$.

4. NP-Completeness:
   The problem of determining whether a graph contains a Hamiltonian cycle is NP-complete. Thus, no efficient algorithm is known to solve it for all graphs.

Construction Methods:

1. Backtracking Algorithm:
   Recursively attempt to build a Hamiltonian path or cycle by exploring all possible routes.
2. Heuristic Approaches:
   Algorithms like nearest neighbor, greedy approaches, or simulated annealing can be used for specific applications (e.g., traveling salesman problem).

Comparison with Eulerian Paths and Cycles:

• Eulerian properties involve edges, while Hamiltonian properties involve nodes.
• A graph may have an Eulerian cycle/path without having a Hamiltonian cycle/path, and vice versa.

Examples:

• Eulerian and Non-Hamiltonian Graph: A complete graph $K_4$ with one edge removed has an Eulerian cycle but no Hamiltonian cycle.
• Hamiltonian and Non-Eulerian Graph: A graph in the form of a triangle with a single additional “tail” edge has a Hamiltonian path but no Eulerian path.

Key Differences Between Eulerian and Hamiltonian Properties