networkx.algorithms.graphical.is_valid_degree_sequence_erdos_gallai¶

is_valid_degree_sequence_erdos_gallai
(deg_sequence)[source]¶ Returns True if deg_sequence can be realized by a simple graph.
The validation is done using the ErdősGallai theorem [EG1960].
 Parameters
deg_sequence (list) – A list of integers
 Returns
valid – True if deg_sequence is graphical and False if not.
 Return type
Notes
This implementation uses an equivalent form of the ErdősGallai criterion. Worstcase run time is \(O(n)\) where \(n\) is the length of the sequence.
Specifically, a sequence d is graphical if and only if the sum of the sequence is even and for all strong indices k in the sequence,
\[\sum_{i=1}^{k} d_i \leq k(k1) + \sum_{j=k+1}^{n} \min(d_i,k) = k(n1)  ( k \sum_{j=0}^{k1} n_j  \sum_{j=0}^{k1} j n_j )\]A strong index k is any index where d_k >= k and the value n_j is the number of occurrences of j in d. The maximal strong index is called the Durfee index.
This particular rearrangement comes from the proof of Theorem 3 in 2.
The ZZ condition says that for the sequence d if
\[d >= \frac{(\max(d) + \min(d) + 1)^2}{4*\min(d)}\]then d is graphical. This was shown in Theorem 6 in 2.
References