Graph and in-Degree and Drawing

Question

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one directed edge), we want to check for how many of the following we have a corresponding graph. the vertex number start from 1 to n and the degree sequence are sort by vertex numbers.

a) $d_{in}=(0,1,2,3), d_{out}=(2,2,1,1)$

b) $d_{in}=(2,2,1), d_{out}=(2,2,1)$

c) $d_{in}=(1,1,2,3,3), d_{out}=(2,2,3, 1,2)$

I want to find a nice way instead of drawing graph.

for (C):

Answer 1

Hints:

How many total directed edges does (a) and (c) have. What does that imply about the digraph? What should the sum $d_{in}+d_{out}$ be for any vertex in these cases?

(b) has too many edges!

Answer 2

Consider the sequence dtotal formed by summing the two sequences together;

dtotal is (2, 3, 3, 4), (4, 4, 2), (3, 3, 5, 4, 5)

Then note that each of these sequences must not contain any number larger than or equal to the number of terms in the sequence.

For example, the 4 in the first sequence would be unconstructible because there are only 4 vertices in the graph, while that vertex with total degree 4 needs to be connected to 4 other distinct vertices (since loops and multiple edges not allowed)

Similar arguments apply for the next two cases. For more information, do a search on degree sequences.