Let $G=K_k$ be the complete graph on $k$ vertices. Consider triangles (subgraphs induced by three vertices) which intersect pairwise in at most one vertex. What is the maximum number of these that one can find, as a function of $k$. Please provide an explanation of your answer.

  • 2
    $\begingroup$ As many as you’d hope if the divisibility works out. Namely, (n choose 2)/3 triangles. These are called Steiner triple systems. If the divisibility doesn’t work out, you can still get a ton of them in there. See arxiv.org/pdf/1504.02909.pdf for an overkill thing. $\endgroup$ – Pat Devlin May 10 '19 at 21:49
  • 1
    $\begingroup$ @PatDevlin Thanks. $\endgroup$ – EGME May 10 '19 at 21:51
  • $\begingroup$ See also “triangle decomposition.” $\endgroup$ – Pat Devlin May 10 '19 at 21:53
  • 1
    $\begingroup$ In spite of the downvotes, the reference is extremely useful, so I am glad I asked the question $\endgroup$ – EGME May 11 '19 at 8:38

Your Answer

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

Browse other questions tagged or ask your own question.