# Coloring Vertices

The other day, I came across this problem on Twitter: How many distinct ways are there to color the vertices of a cube, such that exactly four are one color and the other four are a second color?

I played around a bit first. My first task was to list all the possible combinations, and then I tried to remove rotations. Assuming I didn’t make any mistakes, I came up with seventy combinations of eight dots with four red and four green (this does happen to be the central number on the eighth row of Al-Karaji’s Triangle, so I’ll assume I’m right).

As I started to work through the duplicates, I noticed some patterns, so I decided to try to figure out the possibilities more systematically.

I realized we could see the cube as a “front” and a “back”; ultimately, we could rotate a cube so that any of the six faces would be the “front”. A front face has four vertices, any number of which could be red.

However, if the front face has zero reds, all of the reds would be on the back, and we could rotate the cube to reverse front and back. So we can reduce the possibilities by requiring that the front has 4, 3, or 2 reds (1 red on the front means 3 on the back).

For four reds on the front, there is only one possibility.

For three reds on the front, we can orient the cube so that the upper right is green. The back side would have one red, and there are four logical possibilities for where to put it.

For two reds on the front, there are two possibilities: They are along the same edge or they aren’t. Taking the case that they’re along the same edge, neither of the two reds on the back can share a face with that edge, or there would be a face with three reds, which is covered in the last paragraph. Removing those cases, there’s only one possibility (the middle top image above, the third image in the second row below).

Taking the case that they’re not along the same edge: If the two reds on the back share an edge, they’ll form a three-face with one of the front reds. If the two reds are on the same diagonal as the front, this will be a rotation of the situation in the previous paragraph. So that leaves the situation that they’re on the opposite diagonal (the lower right above, the lower left below).

So that leaves us with just seven to consider: All others will be orientations of these. The question is whether any of the four three-faces will be orientations of the others.

The answer to this is no: These seven configurations (red is solid in my diagrams) are all distinct, and an exhaustive list.

Extension questions:

1. How many distinct ways (where different orientations are the same “way”) can we color vertices red and green, with any number of reds? Zero and one red (and hence seven and eight reds) are trivial, one distinct way each. That leaves two and three to examine (five and six would be the same).
2. How many distinct ways can we color the vertices with up to eight colors, given any number of each?

EDIT: For the first extension question above, the values are three for two (or six) reds and four for three (or five) reds. In the diagram below, a solid dot represents a fixed red, circles represent distinct reds, and ex’d vertices (in the last two rows) represent duplications. The third row represents four reds, generating the same set as above. This means if you wanted a set of dice such that you could orient it to any possible distribution, you’d need 25 (1 + 1 + 3 + 4 + 7 + 4 + 3 + 1 + 1) distinct dice for the 256 possible red/green distributions. 