Given a finite non-decreasing sequence \(\texttt {d}=(d_1,\ldots ,d_n)\) of natural numbers, the Graph Realization problem asks whether d is a graphic sequence, i.e., there exists a labeled simple graph such that \((d_1,\ldots ,d_n)\) is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence \(\texttt {d}=(d_1,\ldots ,d_n)\) of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints \(\mathcal {L}\) composed of pairs \((S_j,\ell _j)\) where \(S_j\subset \{v_1,\ldots ,v_n\}\) , and \(\ell _j\) is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set \(V=\{v_1,\ldots ,v_n\}\) such that \(v_i\) has degree \(d_i\) and \(\partial (S_j)\) is an edge cut of size \(\ell _j\) , for each \((S_j,\ell _j)\in \mathcal {L}\) . We show that such a problem is polynomial-time solvable whenever each \(S_j\) has size at most three. Conversely, assuming P  \(\ne \)  NP, we prove that it cannot be solved in polynomial time when \(\mathcal {L}\) contains pairs with sets of size four, and our hardness result holds even assuming that each \(d_i\) of d equals 1.