combinatorics / Graph theory
The imbalance of an edge uv of a finite simple graph is the absolute difference of the degrees of u and v. Kozerenko and Skochko conjectured that the multiset of all edge imbalances is graphic - realizable as the degree sequence of some graph - whenever every edge has positive imbalance. Proved.
Temporal state
No reconciled state yet.
Append-only history
The key step is a lower bound on the truncated imbalance sum, which yields every Erdos-Gallai inequality for the sorted imbalance list; a parity computation finishes it.
Research memory
The imbalance of an edge uv of a finite simple graph is the absolute difference of the degrees of u and v. Kozerenko and Skochko conjectured that the multiset of all edge imbalances is graphic - realizable as the degree sequence of some graph - whenever every edge has positive imbalance. Proved.
The key step is a lower bound on the truncated imbalance sum, which yields every Erdos-Gallai inequality for the sorted imbalance list; a parity computation finishes it.
Evidence graph
No public relationships recorded yet.