# Counting triangles with small intersection in a complete graph

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.

• 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. – Pat Devlin May 10 '19 at 21:49
• @PatDevlin Thanks. – EGME May 10 '19 at 21:51
• See also “triangle decomposition.” – Pat Devlin May 10 '19 at 21:53
• In spite of the downvotes, the reference is extremely useful, so I am glad I asked the question – EGME May 11 '19 at 8:38