graph theory
Two examples of such graphs with the minimum number of edges are two 4-cliques (each with 6 edges) or a cube. But why is 12 the minimum? Can this be proven?
EDIT: now that someone has disproven my cube example (not sure what I was thinking), I suspect it might be that all graphs with $n$ vertices where 2 out of any 3 vertices are adjacent consist of 2 cliques of size $\lfloor \frac{n}{2}\rfloor$ and $\lceil\frac{n}{2}\rceil$, respectively. Not sure if that is right, though.
So we can see that if we let $n$ and $x$ be a natural number then,
Height 0 - $2^0$
Height 1 - $2$ $\le$ n $\le $$3$
Height 2 - $4$ $\le$ n $\le $$7$
Height 3 - $8$ $\le$ n $\le $$15$
Height 4 - $16$ $\le$ n $\le $$31$
Using mathematical deduction we can conclude,
Height x - $2^x$ $\le$ n $\le $$2^{x+1}-1$
And since we want the least number of terms for the minimum height of the graph we take into consideration the term on the left of the inequality. Further, in order to get the term of the least number of vertices of a given height n must equal to $2^x$ and so,
$n=$ $2^x$ $\Longrightarrow$ $\log_2{n}$ $=x$
Therefore in order to get the least number in each interval we can conclude,
$\lfloor \log_2{n} \rfloor$ $=$ $x$
Notice that the sum of the number of edges in the original gragh $G$ and the complement graph $G'$ must be equal to the number of edges in a complete graph with the number of vertices being the number of vertices in $G$. This is because $G'$ will only contain edges not included in $G$.
Thus if the number of vertices in $G$ is $V$, then the total number of edges is $\frac{V(V-1)}{2}$. Since
$$ 15+13 = 28 = \frac{56}{2} = \frac{8(8-1)}{2} $$
Therefore there must be 8 vertices in the graph.
Best Answer
If every vertex has at least $3$ incident edges, then that makes $24$ incident (vertex,edge) pairs. Since each edge contributes only $2$ such pairs, we have at least $12$ edges, as required.
So suppose, from now on, that some vertex $P$ doesn't have at least $3$ incident edges. If $P$ has only one incident edge or none, then there are $6$ or more vertices not adjacent to $P$. Every two of these $6$ must be adjacent, because any two that are not adjacent would, when combined with $P$, constitute three vertices with no adjacency. So the number of edges would be at least $\binom62=15$, which is more than enough.
There remains the case that $P$ has exactly two incident edges, say $PQ$ and $PR$. Among the $5$ vertices other than $P,Q,R$, every two must be adjacent, lest they and $P$ form three points with no adjacencies. So that gives us $\binom52=10$ edges among those $5$ vertices. Together with the edges $PQ$ and $PR$, we have $12$, as required.