World's most popular travel blog for travel bloggers.

# [Solved]: Maximum edges in degree-restricted digraph

, ,
Problem Detail:

How many edges can there be in a loop-free, asymmetric $n$-vertex digraph, if each node can have maximum total degree $k$ and minimum total degree $m$?

That is,

1. There are no edges $(v,v)$ (self-loops),
2. if there is an edge $(u,v)$, there is no edge $(v,u)$,
3. $d_{\mathrm{in}}(v) + d_{\mathrm{out}}(v)\leq k$ for every vertex $v$, and
4. $d_{\mathrm{in}}(v) + d_{\mathrm{out}} \geq m$ for every vertex $v$.

#### Answered By : Yuval Filmus

The question has changed and will probably change again in the future. It wasn't clear to start with, so the question I was trying to answer is:

How many edges can a directed graph on 22 vertices have, if the out-degree is at most 4, and the in-degree is at least 3?

Connect each node $x$ to nodes $x+1,x+2,x+3,x+4$, all indices taken modulo $22$. This satisfies all your conditions and has 88 edges, which is also trivially the maximum.