Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Possible Duplicate:
Maximum number of distinct 3-cliques in a complete graph

What is the number of disjoint edge triangles in a complete graph. For example, if I have a complete graph on 4 vertices, the number of disjoint edge triangles is 2. How do I extend this to a complete graph of n vertices? every edge is in exactly one triangle.

share|improve this question
2  
I disagree or I don't understand. If you have a complete graph on 4 vertices, there are only 6 total edges, so the most edge disjoint triangles you could have would be 2. But, once you pick any triangle, the 3 edges left do not form another one. – Graphth Oct 14 '12 at 22:24
When you say disjoint, do you allow the triangles to have vertices in common? And how do you get two disjoint edge triangles in $K_4$, even if you do allow common vertices? There are only six edges, and if three of them form a triangle, the remaining three don’t. – Brian M. Scott Oct 14 '12 at 22:25
what i meant was that every edge is in exactly one triangle. – graph_tizzy Oct 14 '12 at 22:31
Any two triangles in $K_4$ have an edge in common, so the maximum number of edge-disjoint triangles in $K_4$ is $1$, not $2$. – Brian M. Scott Oct 14 '12 at 22:34
consider a connected graph on 4 vertices - K4. If the nodes are marked ABCD clockwise, then the 2 disjoint edge triangles are ADC and ABC – graph_tizzy Oct 14 '12 at 22:39
show 1 more comment

marked as duplicate by Douglas S. Stones, Alexander Gruber♦, Fabian, Davide Giraudo, Chris Eagle Dec 31 '12 at 12:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 0 down vote

The question was asked and answered at MathOverflow last year, http://mathoverflow.net/questions/81414/how-many-edge-disjoint-cycles-of-length-3-are-in-the-complete-graph

share|improve this answer
1  
Coincidentally, that result was just recently referred to in this math.SE question. – joriki Oct 14 '12 at 22:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.