Erdős–Gallai theorem
E554299
The Erdős–Gallai theorem is a fundamental result in graph theory that characterizes which sequences of nonnegative integers can occur as the degree sequences of simple graphs.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph theory theorem
ⓘ
mathematical theorem ⓘ |
| appliesTo | simple undirected graphs ⓘ |
| assumes | sequence of nonnegative integers in nonincreasing order ⓘ |
| characterizes | degree sequences of simple graphs ⓘ |
| classification | characterization theorem ⓘ |
| concerns | existence of a simple graph with given degrees ⓘ |
| conditionType | inequality conditions ⓘ |
| countryOfOrigin | Hungary NERFINISHED ⓘ |
| dealsWith |
finite simple graphs
ⓘ
nonnegative integer sequences ⓘ |
| field | graph theory ⓘ |
| givesNecessaryAndSufficientConditionFor | a sequence to be graphical ⓘ |
| hasApplication |
design of networks with specified degree distributions
ⓘ
verification of empirical degree sequences in real-world networks ⓘ |
| hasConsequence | characterization of all graphical sequences ⓘ |
| hasGeneralization |
results on degree sequences of directed graphs
ⓘ
results on degree sequences of hypergraphs ⓘ |
| hasProofTechnique |
combinatorial arguments
ⓘ
induction on number of vertices ⓘ |
| implies | parity condition on degree sums ⓘ |
| importance | fundamental result in graph theory ⓘ |
| inequalityForm | for all k, sum_{i=1}^k d_i ≤ k(k−1) + sum_{i=k+1}^n min(d_i,k) ⓘ |
| involvesConcept |
degree of a vertex
ⓘ
graphical sequence ⓘ nonincreasing sequence ⓘ simple graph ⓘ |
| languageOfOriginalPublication | Hungarian ⓘ |
| mathematicalDomain |
combinatorics
ⓘ
discrete mathematics ⓘ |
| namedAfter |
Paul Erdős
NERFINISHED
ⓘ
Tibor Gallai NERFINISHED ⓘ |
| relatedTo |
Havel–Hakimi algorithm
NERFINISHED
ⓘ
Turán-type extremal problems ⓘ graph realization algorithms ⓘ |
| requires |
Erdős–Gallai inequalities to hold for all k
ⓘ
even sum of degrees ⓘ |
| statesThat | a nonincreasing sequence d1,…,dn of nonnegative integers is graphical if and only if the sum of the di is even and certain inequalities hold for all k between 1 and n ⓘ |
| timePeriod | 20th century ⓘ |
| topic |
degree sequence characterization
ⓘ
graph realization problem ⓘ graphical degree sequences ⓘ |
| usedFor |
constructing simple graphs with given degree sequence
ⓘ
testing whether a sequence is graphical ⓘ |
| usedIn |
degree-based graph models
ⓘ
network theory ⓘ random graph generation with prescribed degrees ⓘ social network analysis ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.