(something like that: 5,1,1,1,1,1 or 6,6,5,4,3,3,3,3,2,1,0,0,0 ) |

GREEN colour of the solution window = the given degree sequence IS graphic. RED = IS NOT graphic.

WHITE = It could not be determined due to an error in the given sequence (possibly

the input field box is empty or there is a comma after the last number, ...).

The calculation is based on the Havel-Hakimi algorithm.

WHITE = It could not be determined due to an error in the given sequence (possibly

the input field box is empty or there is a comma after the last number, ...).

The calculation is based on the Havel-Hakimi algorithm.

A graph (or a simple graph) *G = (V, E)* is a pair of sets *(V, E)* where:

*V = {v*_{1},v_{2}, . . . ,v_{n}} is a nonempty list called the list of vertices of *G*,

and*E = {e*_{1},e_{2}, . . . ,e_{n}} is a list of edges *e = {v*_{i},v_{j}} (unordered pairs of distinct elements of *V*).

The degree*deg*_{G}(v) of a vertex *v*_{i} in an undirected graph *G*

is the number of edges*e* that are incident on the vertex *v*_{i}.

The degree sequence*D = {d*_{1},d_{2}, . . . ,d_{n}} is a list of sorted nonnegative integer numbers.

If we have a nonincreasing, finite degree sequence of nonnegative integers,

we can test whether this degree sequence is graphic by applying the Havel-Hakimi algorithm.

So the question is: Is there a graph*G* with n - vertices,

where degree sequence*d*_{i} = deg_{G}(v_{i}), for every *i = 1,2,...,n* ?

and

The degree

is the number of edges

The degree sequence

If we have a nonincreasing, finite degree sequence of nonnegative integers,

we can test whether this degree sequence is graphic by applying the Havel-Hakimi algorithm.

So the question is: Is there a graph

where degree sequence

It is possible for two topologically distinct graphs to have the same degree sequence.

The example above shows two (isomorphic) graphs that have the same degree sequence = (3,2,2,1,1,1)

There are examples of degree sequences that are graphic:

D = (4,2,2,2,2)

D = (5,1,1,1,1,1)

D = (6,6,5,4,3,3,3,3,2,1,0,0,0)

And few examples of degree sequences that are not graphic:

D = (1,1,1)

D = (4,2,2,2)

D = (4,2,2,2,2)

D = (5,1,1,1,1,1)

D = (6,6,5,4,3,3,3,3,2,1,0,0,0)

And few examples of degree sequences that are not graphic:

D = (1,1,1)

D = (4,2,2,2)

Do you like this online calculator with steps?

We welcome donations of any amount.

Our bank account:

SK8883300000002201224165 (IBAN)

FIOZSKBAXXX (BIC/SWIFT)

Or with Paypal:

Thank you for your support :)

First version 0.01: 14.05.2021

Actual version 1.02: 30.11.2021

(c) 2024 Supremus.sk s.r.o.
Actual version 1.02: 30.11.2021