Inverse Problem for Degree Sequences

Let G = (V,E) be a simple undirected graph, meaning that it has no self-loops (edges of the form (v,v)) and no multiple edges between the same pair of vertices.

For such a graph we can define its degree sequence deg, where each element represents the degree of a vertex.

For example, the graph shown below has degree sequence

deg = (3,1,1,1)

In this exercise we consider the inverse problem: given a degree sequence deg, determine whether it is possible to construct a simple undirected graph with that sequence.

For each of the following statements, determine whether it is True (T) or False (F).

i) deg = (2,2) generates more than one graph.
ii) deg = (2,2,2) generates exactly one graph.
iii) deg = (2,2,2,2,2,2) generates exactly one graph.

Alternatives

a) TTF
b) FTT
c) TFT
d) FTF
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas