The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s in it.
For a (connected) subgraph of a hypercube we say that its *level-vector* is $(n_1,\ldots,n_k)$ if the number of its vertices with minimum weight is $n_1$, with minimum $+1$ weight is $n_2$ etc.
In other words, $n_1,\ldots,n_k$ is the number of vertices on the non-empty (adjacent) levels of the hypercube.

We say that a graph $G$ *level-uniquely embeds to hypercubes* if the level-vector of every induced subgraph of any hypercube that is isomorphic to $G$ is the same (and there is at least one hypercube that contains an induced subgraph that is isomorphic to $G$).

Is there a graph that level-uniquely embeds to hypercubes but is not a hypercube itself?

**Update 2014.12.28** This has been answered in the negative by Flo, see his answer below.

In fact, for my problem a slightly weaker condition would also suffice. Namely, I am also interested in graphs for which there is an $\alpha\ne -1$ such that for the level-vector $(n_1,\ldots,n_k)$ of every induced subgraph of any hypercube that is isomorphic to the graph it holds that $\alpha$ is the root of the *level-polynomial* $\sum n_ix^i$.

Is there a graph and an $\alpha\ne -1$ such that $\alpha$ is the root of every level-polynomial?

My motivation is that if there existed such a graph on a power of $2$ vertices, then I think it would give an example to the question posed here using this method. I've found some nice induced subhypercubes here, but they were too big for me to verify anything.

*The text below is an exposition of the question by Wlodzimierz, edited by me*

Let $\ \mathbb B:=\{0\ 1\}.\ $ Let $\ \mathbb B^n\ $ be the $n$-cube. The elements of the $n$-cube are called vertices. The weight $\ \sum x\ $ of a vertex $\ x:=(x_1\ldots x_n)\in\mathbb B^n\ $ is defined as the sum of the coordinates, $\ \sum x := \sum_{k=1}^n x_k.\ $ Given an arbitrary set $\ A\subseteq\mathbb B^n,\ $ define the weigram $\ w_A:\mathbb Z\rightarrow\mathbb Z,\ $ where $\ w_A(k)\ $ is the number of vertices $\ x\in A\ $ of weight $\ k,\ $ for every $\ k=0\ldots n;\ $ also $\ w_A(k):=0\ $ whenever $\ k<0\ $ or $\ k>n.\ $

Consider arbitrary $\ A\ \subseteq \mathbb B^n, \ B\ \subseteq \mathbb B^m. $ We say that $\ B\ $ is a weight-shift of $\ A\ $ $\ \Leftarrow:\Rightarrow\ \exists_{d\in\mathbb Z}\forall_{k\in\mathbb Z}\ w_B(k) = w_A(k+d)$.

Now let's introduce the graph structure in the $n$-cube. Its edges are pairs $\ \{a\ b\}\subseteq\mathbb B^n\ $ such that $\ a\ b\ $ have exactly one coordinate different (i.e. $\ \sum |a-b| = 1$). Every $\ A\subseteq\mathbb B^n\ $ is considered to be a graph induced by the $n$-cube graph. Two subsets of the $n$-cube are considered to be isomorphic $\ \Leftarrow:\Rightarrow\ $ they are isomorphic as graphs.

QUESTIONS(consider implicitly the versions for connected graphs too, or especially for the connected graphs):

- Is there set $A\ne \emptyset, \mathbb B^n$, such that every $\ B\subseteq \mathbb B^m\ $ which is isomorphic to $\ A\ $ is a weight-shift of $\ A?\ $
- Can you describe all sets $\ A\ $ as above?
- Questions related to the roots of the polynomials $\ \sum_k w_A(k)\cdot t^k\ $ (see above the part one).