A partition {a_1, ..., a_n} is called graphical if there exists a graph G having degree sequence {a_1, ..., a_n}. The number of graphical partitions of length n is equal to the number of n-node graphs that have no isolated points. The numbers of distinct graphical partitions corresponding to graphs on n = 1, 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148, ... (OEIS A095268). A graphical partition of order p is one for which the sum of degrees is p. A p-graphical partition only exists for even p. It is possible for two topologically distinct graphs to have the same degree sequence, an example of which is illustrated above.

cut | degree sequence | isolated point | spectral graph partitioning