IsGraphicSequence - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory

 IsGraphicSequence

 Calling Sequence IsGraphicSequence(L)

Parameters

 L - list of integers

Description

 • 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.

Examples

 > $\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]$ (1)
 > $\mathrm{IsGraphicSequence}\left(L\right)$
 ${\mathrm{true}}$ (2)
 > $G≔\mathrm{SequenceGraph}\left(L\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected graph with 8 vertices and 15 edge\left(s\right)}}$ (3)
 > $\mathrm{sort}\left(\mathrm{DegreeSequence}\left(G\right)\right)$
 $\left[{2}{,}{2}{,}{3}{,}{3}{,}{4}{,}{4}{,}{5}{,}{7}\right]$ (4)