Graph Labelings in Boolean Lattices

A graph \(G\) is said to be embeddable in a set \(X\) if there exists a mapping \(f\) from \(E(G)\) to the set \(\mathcal{P}(X)\) of all subsets of \(X\) such that if we define a mapping \(g\) from \(V(G)\) to \(\mathcal{P}(X)\) by letting \(g(x)\) be the union of \(f(e)\) as \(e\) ranges over all edges incident with \(x\), then \(g\) is injective. We show that for each integer \(k \geq 2\), every graph of order at most \(2^k\) all of whose components have order at least \(3\) is embeddable in a set of cardinality \(k\).