The $n$-dimensional hypercube $Q_n$ is the graph whose vertex set is $\{0, 1\}^n$ and whose edge set is the set of pairs that differ in exactly one coordinate. A graph is called cubical if it is a subgraph of $Q_n$ for some $n$. We know that $|V(Q_n)|=2^n$ and $|E(Q_n)|=n 2^{n-1}$, so $|E(Q_n)|=\frac{1}{2}|V(Q_n)|\log_2 |V(Q_n)|$. Graham [On primitive graphs and optimal vertex assignments. Ann. New York Acad. Sci. 175 (1970), 170--186] showed that a $t$-vertex cubical graph can have at most $(1+o(1))\frac{1}{2}t\log_2 t$ edges. My question is: can a $2^{n}$-vertex cubical graph have more than $n2^{n-1}$ edges? In general, for $2^{n-1}< t \leq 2^{n}$, can a $t$-vertex cubical graph have more edges than the subgraph of $Q_n$ induced by any $t$ vertices?

Comment. I have read the paper of Graham again, and I realized that he in fact proved that a $t$-vertex cubical graph can have at most $W(t-1)$ edges, where $W(t-1)=w(1)+\ldots+w(t-1)$ and $w(i)$ is the number of 1's in the binary expansion of $i$. This upper bound can be achieved by some $t$ vertices in $Q_n$ for $2^{n-1}< t \leq 2^{n}$. So my question is solved. Fedor Petrov gave a very nice proof of the statement that a $t$-vertex cubical graph can have at most $\frac{1}{2}t\log_2 t$ edges. Thanks a lot!