In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices?  Input digraph with $n$ vertices have following degree criteria :There are no edges $(v,v)$ (self-loops),If there is an edge $(u,v)$, there is no edge $(v,u)$,$d_{\mathrm{in}}(v) \leq 2$ for every vertex $v$, and$d_{\mathrm{out}}(v) \leq 2$ for every vertex $v$.$d_{\mathrm{in}}(v) + d_{\mathrm{out}} \geq 3$ for every vertex $v$.After adding one vertex, the digraphs with $n$+1 vertices should also follow same degree criteria. Is there any way to mathematically express the number of possibilities?My approach:I come to know that, In a directed graph with n vertices has total degree k, can have at-most nk/2 edges. So for example (Specific Case) If the original digraph is having 20 vertices and total degree of each vertex is 3 (minimum case). That means maximum edge possible is 30. When I add one node to the digraph, total vertices will be 21 and if i take total degree to 4(maximum). Then maximum possible edges will be 42. Which means there is 12 (42 - 30) possible position where I can add new edge.So finally I have 12 free positions(indegree and outdegree) and I can add maximum 4 and minimum 3 edges at once and then I will calculate possible combinations...Is this approach correct
How many ways are there to add a node to a digraph?
graph theory;combinatorics
Since we are not treating isomorphic graphs as identical, my advice in the comments to try all the options was bad.Let $G$ be the original graph. Let $A$ be the set of vertices in $G$ that can accept an extra incoming edge and let $B$ be the set of vertices that can accept an extra outgoing edge. Every vertex has total degree 3 or 4 and no vertex in the new graph can have degree more than 4. This means that no vertex of $G$ can have more than one edge added to it, so $A\cap B=\emptyset$.Now, consider adding a new vertex $x$ to $G$.  By the degree conditions, $x$ must be connected to $G$ in one of the following ways:it sends one edge to $A$ and receives two from $B$;it sends two edges to $A$ and receives one from $B$;it sends two edges to $A$ and receives two from $B$.Working out the total number of ways from here is simple combinatorics.