Message Boards Message Boards


Finding Integer triangulated polygons

Posted 4 years ago
2 Replies
4 Total Likes

At the Demonstration Wheel Graphs with Integer Edges I've started collecting polygons made from integer triangles. I'm looking at subtask of Harborth's conjecture, namely that any triangulated planar graph (a planar graph entirely made of triangles) can be represented with integer edges. If that's true, then any interior vertex is the center of a wheel graph with integer edges. If I have a database of integer wheel graphs, then I can start piecing them together to make larger integer graphs.

An Integer Wheel Hexagon

This Demonstration is a start at that database. My search method is brute force, and building this database took weeks of computer time. Does anyone have a faster method?

2 Replies
Posted 4 years ago

I don't know but maybe this article Minimal Polynomials for the Coordinates of the Harborth Graph, even if limited to the case of 4-regular planar unit-distance graph, could give you some fresh ideas.


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.

   -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]

Looking at that, I noticed

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]

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.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract