偶维超立方体Q_k中含2^{k-1}+s个顶点子图的最大边数探究

假设k是偶数，考虑k维超立方体$Q_k$的子图G，它包含$2^{k-1}+s$个顶点，其中$1\le s\le 2^{k-1}-1$。我想知道，这个子图G最多能包含多少条边？

目前有定理给出了一个上界：G的平均度不超过$v_G\log_2 v_G$，由此可以推导出边数至多为$\lfloor\frac{v_G\log_2 v_G}{2}\rfloor$。但疑问在于——这个上界是不是最优的？有没有办法构造出一个子图G，刚好达到这个边数上限？

举个具体的例子，当$s=1$时，原提问者原本打算展开说明“要最大化$2^...$”，不过内容并未完结。

内容的提问来源于stack exchange，提问作者Connor