📂Graph Theory

Erdős–Gallai Theorem

Buildup

1. 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$.
2. 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}^{n} 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 ¹

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.