Choosing the vertices of a regular hexagon, how many ways are there to form four triangles such that any two triangles share exactly one vertex

combinatoricsgraph theory

In other words, how many ways are there to choose four $3$-combinations of a $6$-set, such that each two combinations contain exactly one common element, modulo dihedral group $D_6$?

For example, $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ and $\{2,3,4\}, \{2,5,6\},\{3,5,1\}, \{4,6,1\}$ belong to the same class, but $\{1,2,3\}, \{1,4,5\},\{2,5,6\}, \{3,4,6\}$ does not.

Context: I am considering partitions of a $4$-set and partially ordering them by refinement. The result is a lattice which I am trying to visualize by a $3$D graph. The most interesting part of the graph involves a square and a regular hexagon. For example: $\{1,2,3\}, \{1,4,5\},\{2,4,6\}, \{3,5,6\}$ leads to this visualization.

Edit: I have categorized all $30$ possibilities into $5$ orbits:

  1. (three edges of the hexagon missing, $4$ elements) $124.135.256.346, 125.134.246.356, 135.146.236.245, 136.145.235.246.$

  2. (two edges, one long diagonal missing, $6$ elements) $123.145.246.356, 124.135.236.456, 125.136.246.345, 126.135.245.346, 134.156.235.246, 135.146.234.256.$

  3. (one edge, two short diagonals missing, $12$ elements) $123.145.256.346, 123.146.245.356, 124.136.235.456, 124.136.256.345, 124.156.235.346, 125.134.236.456, 125.146.234.356, 125.146.236.345, 126.134.245.356, 126.145.235.346, 134.156.236.245, 136.145.234.256.$

  4. (two short and one long diagonal missing, $6$ elements) $123.146.256.345, 123.156.245.346, 124.156.236.345, 125.136.234.456, 126.134.235.456, 126.145.234.356.$

  5. (three long diagonals missing, $2$ elements) $123.156.246.345, 126.135.234.456.$

Best Answer

Four triangles means twelve slots to fill. There are six vertices to place in those slots. No vertex can occur three times, because it can't occur twice in a single triangle, and if there are three triangles which share that vertex and no other then there must be six other distinct vertices. In short: by two applications of the pigeonhole principle, each vertex is in precisely two of the triangles.

Therefore each vertex has four neighbours, so is missing precisely one neighbour, and they pair up: the overall graph is $K_6$ from which three non-adjacent edges have been removed.

The possibilities for the missing edges modulo the dihedral group are:

  1. Three edges of the hexagon (e.g. $0-1, 2-3, 4-5$)
  2. Two edges of the hexagon and one long diagonal (e.g. $0-1, 2-5, 3-4$)
  3. One edge of the hexagon and two short diagonals (e.g. $0-1, 2-4, 3-5$)
  4. Two short diagonals and one long diagonal (e.g. $0-2, 1-4, 3-5$)
  5. Three long diagonals (e.g. $0-3, 1-4, 2-5$)
Related Question