Proposition: Let C denote the graph of the regular 600-cell. Up to graph
isomorphism, the subgraph induced by two colours of a 5-colouring of the
vertices of C is the only induced subgraph of C with at least 48 vertices
and maximum degree 3.
Proof (incomplete): Suppose we have a subgraph G of C that satisfies the
conditions. Each edge in C connecting a vertex in G and a vertex not in G
is to be assigned a weight, based on i, the number of vertices in G among
the 5 vertices in C that are adjacent to both those vertices. Simply put,
the result will follow from considerations of the weighted sum over all
such edges. Some numerical verifications have been left out.
Since G's maximum degree is 3, i is at most 3. Let {y_i} denote the weights.
We will apply y_0 = y_1 = 4, y_2 = 3 and y_3 = 2. The necessary conditions
for the argument to work are
y_0 > y_2
2 y_1 < 3 y_2
y_0 + y_2 < 2 y_1
y_1 + y_2 > 3 y_3
2 y_1 > y_2 + 2 y_3
y_0 + y_1 + y_3 > 3 y_2
and our choice is the simplest integral solution.
One way to calculate the weighted sum is to add together the contributions
from each vertex of G. For instance, a vertex of degree 1 would contribute
6 y_0 + 5 y_1 = 11 * 4 = 44. The smallest possible contribution is from a
vertex of degree 3 for which no two of its neighbours are adjacent. The
contribution from such a vertex is 3 y_1 + 6 y_2 = 3 * 4 + 6 * 3 = 30.
Alternatively, one can add together the contributions from the vertices
_not_ in G. It can be verified that in this case, the _maximal_ contribution
is 20, attained when the neighbours that are in G form a path of length 6.
Since the two summations must give the same result, it follows that the number
of vertices in G can not exceed 48 (note that 48 * 30 = (120 - 48) * 20).
Furthermore, for any vertex in C, the intersection of its 12 neighbours and G
must be as described (three mutually non-adjacent vertices if the vertex is in
G, otherwise six vertices forming a path) if this is to be attained. It can
then be verified that this implies the claim of the proposition. [ ]