Erdős–Gallai Theorem
Buildup
- A set that includes duplicates of the degrees of a graph $G$ is called a Graph Score, and the sequence $G$ sorted in descending order (non-increasing) of a graph score is called the Degree Sequence of $G$.
- If there exists a graph $G$ that satisfies the following, with a sequence $D = (d_{1} , \cdots , d_{n})$ of non-increasing natural numbers and $n$ vertices $v_{1} , \cdots , v_{n}$, then $D$ is said to be Graphic, and the graph $G$ is referred to as the Realisation of $D$.
For instance, given a graph like the one above $G_{0}$, the graph score would be $$ \left\{ 1,5,3,5,2,1,5,2 \right\} $$ and the degree sequence, sorted in non-increasing order, would be as follows: $$ D_{0} = (5,5,5,3,2,2,1,1) $$
Any mathematician would naturally be interested in whether it’s possible to construct a graph solely from the degree sequence. If it is possible, that means the sequence can originate a graph, introducing concepts like being Graphic or Graphable. Continuing with the example above, $G_{0}$ can be seen as one of the realisations of $D_{0}$. [ NOTE: A realisation does not need to be unique. ]
Thus, the equivalence condition for a sequence being graphic is clarified with the following theorem.
Theorem
Erdős–Gallai Theorem
A sequence $(d_{1} , \cdots , d_{n})$ being graphic is equivalent to satisfying the following two conditions simultaneously. $$ \sum_{i=1}^{k} d_{i} \in 2 \mathbb{Z} \\ \sum_{i=1}^{k} d_{i} \le k ( k-1) + \sum_{i=k+1}^{n} \min (k, d_{i}) , \qquad 1 \le k \le n $$
- $2 \mathbb{Z}$ denotes an even set.
Proof 1
Omitted.
See Also
However, this only guarantees the existence of a realisation, not what that realisation looks like specifically, so it’s necessary to explore directly with methods like the Havel-Hakimi algorithm. This is similar to how finding a specific Euler trail in an Eulerian graph requires the use of the Fleury’s algorithm.