# Simple conjecture about graphs where at least 2 out of any 3 vertices are adjacent

A conjecture I am thinking about:

Any graph with $$n$$ vertices in which at least 2 out of any 3 vertices are adjacent, where no such graph with fewer edges is possible, consists of 2 connected components which are cliques of size $$\lfloor \frac{n}{2}\rfloor$$ and $$\lceil\frac{n}{2}\rceil$$.

This seems like something that would be easy to prove if it were true, but I tried using induction on n and had some trouble working back to the IH. On the other hand, I can't think of any counterexamples.

Any thoughts?

• Why wouldn't any pair of cliques work? Jul 2 '19 at 1:49
• In the graphs you describes as having two connected components that are cliques of nearly equal size, there would be sets of three vertices all adjacent when $n\ge 5$. So perhaps you mean to require at least two adjacent vertices in any subset of three. But then we cannot prove the two cliques are nearly equal in size, and indeed there might be only one connected component. Jul 2 '19 at 1:51
• Sorry I left out part of the conjecture and should have put 'at least' to make it clearer... in fact for the original statement any complete graph would also work Jul 2 '19 at 1:53
• the path graph on 3 vertices works Jul 2 '19 at 1:58
• But $P_2$ and a single vertex would have 1 edge, whereas $P_3$ has two edges so $P_3$ does not have the minimum number of edges Jul 2 '19 at 2:00

If we think about the complement $$H=\bar{G}$$ then the condition is that $$H$$ has no triangle, and we want to maximize the number of edges of $$H$$. This is Turán's theorem. $$H$$ is (uniquely) a complete bipartite graph with parts as equal as possible. Hence $$G$$ is the disjoint union of two cliques with sizes as equal as possible, as conjectured.

• Wow, thanks. I had never heard of that theorem before. Jul 2 '19 at 2:28