I wanted to add order 3 wheel graphs to the demo demo for everything with an edge length less than 100. That starts running into combinatorial difficulties, so I calculated the distance between the far vertices of two triangles sharing an edge. It's this monstrosity.
Sqrt[(
-a^4 - (b - c)*(b + c)*(d - e)*(d + e) + a^2*(b^2 + c^2 + d^2 + e^2) +
Sqrt[a + b - c]*Sqrt[a - b + c]*Sqrt[-a + b + c]*Sqrt[a + b + c] * Sqrt[a + d - e]*Sqrt[a - d + e]*Sqrt[-a + d + e]*Sqrt[a + d + e]
)/a^2]/Sqrt[2]
Looking at that, I noticed
Sqrt[a + b - c]*Sqrt[a - b + c]*Sqrt[-a + b + c]*Sqrt[a + b + c]
and
Sqrt[a + d - e]*Sqrt[a - d + e]*Sqrt[-a + d + e]*Sqrt[a + d + e]
which I recognized as Hero's formula. It's four times the area, for each of the two triangles.
In order for all those Sqrt[]'s to resolve under the radical, the product of the two 4*areas had to be an integer.
So, I decided I should calculate the area radicals for all those triangles, to see what happened.
Hero[{a_, b_, c_}] := Sqrt[(a + b + c) (a + b - c) (a - b + c) (-a + b + c)]/4;
SquareFreePart[number_] := Times @@ Power @@@ ({#[[1]], Mod[#[[2]], 2]} & /@ FactorInteger[number]);
AreaRadical[{a_, b_, c_}] := SquareFreePart[Numerator[Hero[{a, b, c}]]^2];
I colored the triangles based on the area radicals. So far, in the thousands of wheel graphs I've found, all graphs need only two colors.
I updated the demo to show the radical colorings.