The IsGraphicSequence command returns true if there exists a graph with the specified degree sequence given as input. It returns false otherwise. The strategy is to verify some inequalities due to Erdős, Gallai (1960). A refinement due to Tripathi, Vijai (2003) is implemented which makes the algorithm faster.

To construct a graph with given degree sequence, use SequenceGraph.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$L≔\left[3\,2\,4\,2\,3\,4\,5\,7\right]$

$L≔\left[3\,2\,4\,2\,3\,4\,5\,7\right]$

$\mathrm{IsGraphicSequence}\left(L\right)$

$\mathrm{true}$

$G≔\mathrm{SequenceGraph}\left(L\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 8\; vertices\; and\; 15\; edge(s)}$

$\mathrm{sort}\left(\mathrm{DegreeSequence}\left(G\right)\right)$

$\left[2\,2\,3\,3\,4\,4\,5\,7\right]$