Havel-Hakimi Algorithm Implementation

This is an implementation of the Havel-Hakimi Algorithm to determine if a potential graph degree sequence is graphical or not.

Algorithm Overview

The Havel-Hakimi algorithm is based on the following theorem:

Let A = (s, t₁, ..., tₛ, d₁, ..., dₙ) be a finite list of nonnegative integers in nonincreasing order.

Let A' = (t₁−1, ..., tₛ−1, d₁, ..., dₙ) be a second finite list of nonnegative integers rearranged to be nonincreasing.

Theorem: List A is graphic if and only if list A' is graphic.

How It Works

1. If the given list A is graphic, the theorem will be applied at most n−1 times, setting A := A' in each step
2. After each step, the list may need to be sorted again to maintain nonincreasing order
3. The process terminates when the entire list A' consists of zeros

Graph Construction

Let G be a simple graph with degree sequence A:

• Vertex S has degree s
• Vertices {T₁, ..., Tₛ} have respective degrees {t₁, ..., tₛ}
• Vertices {D₁, ..., Dₙ} have respective degrees {d₁, ..., dₙ}

In each iteration, we construct edges of the graph:

• If it's possible to reduce list A to A', we add edges {S,T₁}, {S,T₂}, ..., {S,Tₛ}

When the list cannot be reduced to a list of nonnegative integers in any step, the theorem proves that the original list is not graphic.

Usage

Use the file Test.py to input a potential degree sequence and determine if a graph with that degree sequence exists.