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?

  • $\begingroup$ Why wouldn't any pair of cliques work? $\endgroup$
    – TomGrubb
    Jul 2 '19 at 1:49
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Jul 2 '19 at 1:51
  • $\begingroup$ 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 $\endgroup$ Jul 2 '19 at 1:53
  • $\begingroup$ the path graph on 3 vertices works $\endgroup$
    – TomGrubb
    Jul 2 '19 at 1:58
  • $\begingroup$ 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 $\endgroup$ 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.

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

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.