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.

  • 1
    $\begingroup$ Do you mean "2 out of any 3 vertices are adjacent..."? $\endgroup$
    – Dave
    Jun 30 '19 at 23:59
  • $\begingroup$ Yes, sorry - I edited the title $\endgroup$ Jul 1 '19 at 0:01
  • $\begingroup$ 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. $\endgroup$ Jul 1 '19 at 0:21
  • $\begingroup$ A cube does have 3 vertices in which none are adjacent. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.