0
$\begingroup$

What's the maximum number of distinct triangles in complete graph of n vertices such that each edge of the graph appears in exactly two triangles? Maybe with the way to construct them?

I hope I phrase the question correctly in the title. For example, for $K_6$, I obtain 10 triangles:

123, 124, 236, 345, 346, 245, 135, 156, 256, 164

which I do not think more can be added. I tried to use various decompositions but I still got nothing. Does anyone know any link or hint that might help? Thanks

$\endgroup$
  • $\begingroup$ Please insert the clear question in the text, not (only) in the title. The situation of $K_6$ is a special one, or we have to solve a problem (which one?!) in a general graph? $\endgroup$ – dan_fulea May 15 at 16:29
  • 5
    $\begingroup$ Each triangle covers three edges. There are $\binom{n}2$ edges, each to be covered twice. Therefore, you must have exactly $$2\cdot \binom{n}2/3=\frac{n(n-1)}3 $$ triangles. Whether or not this is possible is a difficult question. What you are looking for is called a $(n,3,2)$ design. $\endgroup$ – Mike Earnest May 15 at 16:48
  • $\begingroup$ @MikeEarnest: I don't think it is required to use all the edges, though that would be optimal. If there is no $(n,3,2)$ design, the question is to find the largest set of triangles such that each edge used is used (at most) twice. $\endgroup$ – Ross Millikan May 15 at 17:10
  • $\begingroup$ @bms your example is correct. In Mike Earnest's language, you have found a $(6,3,2)$ design. There are $15$ edges in $K_6$, so if you use each twice you will form $10$ triangles. In $K_7$ there are $21$ edges, so you would form $14$ triangles if you can use them all twice. I don't know if you can find a way to do that. $\endgroup$ – Ross Millikan May 15 at 17:12
  • 2
    $\begingroup$ @RossMillikan The question being asked wants each edge to appear exactly twice. Your question is also a good one, but a different one. $\endgroup$ – Morgan Rodgers May 15 at 19:29

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.