# A graph with $8$ vertices where $2$ out of any $3$ vertices are adjacent has a minimum of $12$ edges... why?

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.

• Do you mean "2 out of any 3 vertices are adjacent..."?
– Dave
Jun 30 '19 at 23:59
• Yes, sorry - I edited the title Jul 1 '19 at 0:01
• Well there are 56 ways to choose 3 vertices out of the 8. And for a given edge, there are 56*3=168 ways to select a group of three and decide which two vertices in that group it will join. I'm not sure what you mean, however. Jul 1 '19 at 0:21
• A cube does have 3 vertices in which none are adjacent. Jul 1 '19 at 1:34

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.