Graph and one Sequence challenge

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

Your problem (in its general form) was solved by Péter L. Erdős, István Miklós and Zoltán Toroczkai in this quite recent paper (arXiv version). To quote:

[Let $d_n^+$ and $d_n^-$ denote respectively the out-degree and in-degree of a vertex $v_n$.]

[W]e introduce the notion of normal order: we say that the [bi-degree-sequence] is in normal order if the entries satisfy the following properties: for each $i = 1, \ldots, n−2$ we either have $d^−_i > d^−_{i+1}$ or $d^−_i = d^−_{i+1}$ and $d^+_i \geq d^+_{i+1}$ Clearly, all BDS-s can be arranged into normal order. Note that we made no ordering assumption about node $v_n$ (the pair $d^+_n, d^−_n$).

Theorem 2 Assume that the BDS $(\mathbf{d}^+, \mathbf{d}^-)$ (with $d^+_j + d^-_j > 0, j \in [1,n]$) is in normal order and $d^+_n > 0$ (that is the out-degree of the last vertex is positive). Then $(\mathbf{d}^+, \mathbf{d}^-)$ is bi-graphical if and only if the BDS \begin{align} \Delta^+_k &= \begin{cases}d^+_k & \text{ if } k \neq n \\ 0 & \text{ if } k = n,\end{cases}\\ \Delta^-_k &= \begin{cases}d^-_k-1 & \text{ if } k \leq d^+_n \\ d^-_k & \text{ if } k > d^+_n,\end{cases} \end{align} with zero elements removed (those $j$ for which $\Delta^+_j = \Delta^-_j = 0$) is bi-graphical.

[...]

[C]hoose any vertex $v_n$ with non-zero out-degree from the sequence, arrange the rest in normal order, then make [$d_n^+$] connections from $v_n$ to nodes with largest in-degrees, thus constructing the out-neighborhood of $v_n$ in the (final) realization. Next, remove the vertices (if any) from remaining sequence that have lost both their in- and out-degrees in the process, pick a node with non-zero out-degree, then arrange the rest in normal order. [...]

I hope this helps $\ddot\smile$

Edit: Here is the solution you sought.

(a) This example can be easily drawn. If you want to use the above theorem then the reduction could be as follows:

\begin{align} ((1,1,2,2),(3,2,1,0)) &\leadsto ((1,1,2,0),(2,1,1,0)) \leadsto ((1,1,2),(2,1,1))\\ &\leadsto ((1,1,0),(1,0,1)) \leadsto ((1,0,1),(1,1,0)) \\ &\leadsto ((1,0,0),(0,1,0)) \leadsto ((0,1),(1,0)) \\ &\leadsto ((0,0),(0,0)) \leadsto ((),()) \end{align}

Surely the empty sequence is bigraphical, so the example is bigraphical, but one could stop earlier at $((1,1,2),(2,1,1))$ which is easy enough.

(b) This sequence is not bigraphical. You can observe this as both vertices of out-degree two require two neighbors; that means the third vertex has to receive an edge from both of them, but its in-degree is only one. Using the above theorem you get reduction as follows:

\begin{align} ((2,2,1),(2,2,1)) &\leadsto ((2,2,0),(1,2,1)) \leadsto ((2,0,2),(2,1,1)) \\ & \leadsto ((2,0,0),(1,0,1)) \leadsto ((2,0),(1,1)) \end{align}

and the last sequence is not bigraphical because we disallow loops.

(c) This example also can be drawn (as you did), so the sequence is bigraphical. To give you a reduction using the above theorem:

\begin{align} ((2,1,3,2,2),(3,3,2,1,1)) &\leadsto ((2,1,3,2,0),(2,2,2,1,1)) \leadsto ((2,1,2,0,3),(2,2,1,1,2)) \\ & \leadsto ((2,1,2,0,0),(1,1,0,1,2)) \leadsto ((0,2,1,0,2),(2,1,1,1,0)) \\ & \leadsto ((0,2,1,0,0),(1,0,1,1,0)) \leadsto ((1,0,0,2),(1,1,1,0)) \\ & \leadsto ((1,0,0,0),(0,0,1,0)) \leadsto ((0,1),(1,0)) \\ & \leadsto ((0,0),(0,0)) \leadsto ((),()) \end{align}

Summary: If you have only a few vertices, try to draw an example. When drawing an example or making a reduction: pick any vertex and sort the rest lexicographic order on $(d^-, d^+)$ (that is, first compare in-degrees) after removing any vertices with neither any in-degree or out-degree left. If you want, you can always swap the in-degrees and out-degrees of all vertices (intuitively it is like reversing all the edges).

Finally, if you are allowed to use on exam any theorems you want, and if you want to use the above theorem, be sure to include in your solution a proper reference:

Erdős et al., "A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs", The Electronic Journal of Combinatorics, Vol. 17, 2010.