Let $k$ be an even number. For a $k$-dimensional cube (http://mathworld.wolfram.com/HypercubeGraph.html) $Q_k$, let $G$ be a subgraph of $Q_k$ with $2^{k-1}+s$ vertices, for $1\le s\le 2^{k-1}-1$. I am wondering what is maximum number of edges $G$ can have?
A theorem says average degree of $G$ is at most $v_G\log_2 v_G$, so the number of edges of $G$ is at most $\lfloor\frac{v_G\log_2 v_G}{2}\rfloor$. But is this the best bound? For example when $s=1$, in my mind, to maximize the number of edges on $2^{k-1}+1$ vertices, it should contains a $(k-1)$-dim subcube, say $\{(x_1,\dots,x_{n-1},0):x_i\in\{0,1\}\}$. But then the remaining vertex $(y_1,\dots,y_{n-1},1)$ can have only one edge with the subcube. So this $G$ has only $(k-1)2^{k-2}+1$ edges. But for even $k$, $$\lfloor\frac{v_G\log_2 v_G}{2}\rfloor=\lfloor\frac{(2^{k-1}+1)\log_2 (2^{k-1}+1)}{2}\rfloor\ge \lfloor\frac{(2^{k-1}+1)(k-1)}{2}\rfloor=\frac{(2^{k-1}+1)(k-1)-1}{2}=(k-1)2^{k-2}+\frac{k-2}{2},$$ which is much larger than $(k-1)2^{k-2}+1$ when $k$ is large. Therefore I am asking when $k$ is even and $2^{k-1}+1\le v_G\le 2^{k-1}+2^{k-1}-1$, is the bound $\lfloor\frac{v_G\log_2 v_G}{2}\rfloor$ tight, or is there any other better result?
