havel hakimi theorem

3 min read 18-12-2024

The Havel-Hakimi theorem is a fundamental result in graph theory that provides a surprisingly simple algorithm for determining if a given degree sequence can represent a simple graph. Understanding this theorem offers valuable insights into the structure and properties of graphs. This article will explore the theorem itself, its proof, and its applications.

Understanding Degree Sequences

Before diving into the Havel-Hakimi theorem, let's clarify the concept of a degree sequence. In a simple graph (a graph with no loops or multiple edges between the same two vertices), the degree of a vertex is the number of edges connected to it. A degree sequence is a non-increasing sequence of integers representing the degrees of all vertices in the graph. For example, the degree sequence (4, 3, 2, 1, 0) might represent a graph with five vertices, one having degree 4, one with degree 3, and so on.

The question the Havel-Hakimi theorem answers is: Given a degree sequence, is it graphical? That is, does there exist a simple graph with that degree sequence?

The Havel-Hakimi Theorem

The Havel-Hakimi theorem states:

A non-increasing degree sequence d = (d₁, d₂, ..., d_n) is graphical if and only if the sequence d' obtained by removing the largest degree (d₁) and subtracting 1 from the next d₁ largest degrees is graphical. If any of the resulting degrees become negative, the original sequence is not graphical. The process is repeated until a trivial sequence (all zeros) or a non-graphical sequence is obtained.

Let's break this down:

Start with a non-increasing degree sequence: Arrange the degrees in descending order.
Remove the largest degree (d₁): Take the first element of the sequence.
Subtract 1 from the next d₁ largest degrees: Reduce the next d₁ values by 1. If any value becomes negative, the original sequence is not graphical and the process stops.
Repeat: Apply steps 2 and 3 to the resulting sequence until you reach a sequence of all zeros (graphical) or encounter a negative value (not graphical).

Example

Let's test the degree sequence (4, 3, 2, 1, 0):

(4, 3, 2, 1, 0): d₁ = 4.
Removing d₁ and subtracting 1 from the next four elements gives: (2, 1, 1, 0).
(2, 1, 1, 0): d₁ = 2.
Removing d₁ and subtracting 1 from the next two elements gives: (0, 0, 0).
Since we've reached a sequence of all zeros, the original sequence (4, 3, 2, 1, 0) is graphical.

Proof (Sketch)

A full formal proof of the Havel-Hakimi theorem is beyond the scope of this article, but the core idea is based on induction and the construction of a graph. The "if" part (if the resulting sequence is graphical, the original is too) relies on showing that if a graph exists for the reduced sequence, you can always add a vertex with degree d₁ to create a graph for the original sequence. The "only if" part involves showing that if a graph exists for the original sequence, a corresponding graph can be constructed for the reduced sequence. This involves a clever argument involving removing the vertex with the highest degree and adjusting adjacent vertices accordingly.

Applications

The Havel-Hakimi theorem has various applications:

Network design: Determining if a desired network structure with specific connection requirements is feasible.
Chemical graph theory: Analyzing the structures of molecules represented as graphs.
Social network analysis: Studying the relationships and connections within a social network.
Algorithm design: Used as a subroutine in more complex graph algorithms.

Conclusion

The Havel-Hakimi theorem offers an elegant and efficient algorithm for determining the graphical nature of a degree sequence. Its simple iterative procedure and broad applicability make it a valuable tool in various fields utilizing graph theory. While the formal proof might be challenging, understanding the algorithm and its applications is crucial for anyone working with graphs and their properties.