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!



How many edges can a t-vertex cubical graph have?
Let me try to prove that for every integer $t>0$ the number of edges of a $t$-vertex cubical graph has at most $\frac12 t\log\_2t$ edges.


This is true for $t=1$. So assume (by induction) that $t>1$ and it is proved for smaller number of vertices. Without loss of generality, the vertex set of our graph contains the elements of $\{0,1\}^n$ with last coordinates equal to 0 and equal to 1. So, we may write $t=a+b$ where $a\geqslant b>0$ and $a$, $b$ denote the number of vertices with last coordinates equal to 0 and 1. By induction hypothesis, the number of edges does not exceed $$\frac12a\log\_2a+\frac12b\log\_2b+b,$$
where the last summand corresponds to edges between vertices which differ in the last coordinate. Thus, it suffices to prove the inequality
$$\label{1}
\frac12a\log\_2a+\frac12b\log\_2b+b\leqslant \frac12(a+b)\log\_2(a+b).\tag{1}
$$
Denoting $a=xb$, $x\geqslant 1$, \eqref{1} reads as $$f(x):=(x+1)\log(x+1)-x\log x\geqslant 2\log 2=f(1).\tag{2}\label{2}$$
We have $f'(x)=\log(x+1)-\log x\geqslant 0$, fo $f$ increases that yields \eqref{2}.


