I'm trying to find how many different ways there are to colour the edges of a regular tetrahedron with n colours such that there are no monochromatic triangles.

Certainly for one triangle there must be n choose 3 ways but I'm not quite sure how to generalise this to a tetrahedron.

Any help would be much appreciated!

  • $\begingroup$ is monochromatic one solid colour ie not all faces could be blue? $\endgroup$ – Ben May 21 '13 at 15:58
  • $\begingroup$ You mean coloring the edges? $\endgroup$ – ccorn May 21 '13 at 16:46
  • $\begingroup$ Colouring the edges yes, sorry. Monochromatic triangle would mean every edge is the same colour. Have edited the question now. $\endgroup$ – Wooster May 21 '13 at 17:44

Consider the three edges $e_1$, $e_2$, $e_3$ emanating from the top vertex $v_0$.

(i) You can color $e_1$, $e_2$, $e_3$ using three different colors in $n(n-1)(n-2)$ ways. For each of these colorings you can color the three bottom edges $e_4$, $e_5$, $e_6$ arbitrarily, but not all of them equal. This gives $n(n-1)(n-2)(n^3-n)$ admissible colorings of type (i).

(ii) You can color $e_1$, $e_2$, $e_3$ using two different colors in $3n(n-1)$ ways. The bottom edges then can be colored in $n^2(n-1)-(n-1)$ ways, where the $-(n-1)$ term again discounts the monochromatic bottom triangles. This gives $3 n(n-1)(n^2-1)(n-1)$ admissible colorings of type (ii).

(iii) You can color $e_1$, $e_2$, $e_3$ using a single color in $n$ ways. The bottom edges then can be colored in $(n-1)^3-(n-1)$ admissible ways. This gives $n(n-1)\bigl((n-1)^2-1\bigr)$ admissible colorings of type (iii).

Adding it all up we obtain $N:=n^6-4n^4+6n^2-3n$ admissible colorings.


For one triangle there are actually $n^3-n$ edge colourings, including reflections and rotations.

There are $6$ edges in a tetrahedron, $n^6$ ways to colour the edges, $4$ triangles, $n^4$ colourings with any given triangle monocromatic, $6$ pairs of triangles, $n^2$ colourings with any given pair of triangles both monochromatic, 4 ways to pick $3$ triangles, $n$ colourings with $3$ triangles, hence all triangles, monochromatic, $1$ way to pick $4$ triangles and $n$ colourings with $4$ triangles monochromatic.

The number of $n$-colourings without monochromatic triangles is then $n^6-4n^4+6n^2-3n$.

  • $\begingroup$ I wish I could upvote this twice; it's perfect. $\endgroup$ – MJD May 22 '13 at 0:59
  • 1
    $\begingroup$ @MJD: I tried several times, but I didn't arrive at understanding this answer, even though the result is correct. That's why I posted my own. Can you shed some light on it? $\endgroup$ – Christian Blatter May 22 '13 at 16:35
  • $\begingroup$ I agree that it is highly abbreviated. I had to read carefully before I understood. Does it help if I explain that it's an application of the inclusion-exclusion formula, or should I provide more detail? $\endgroup$ – MJD May 22 '13 at 16:50

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.