# Divide $n$-gon into triangles

Find all positive integer $n \geq3$ such that the convex $n$-gon can be divided by its $n-3$ diagonals into $n-2$ triangles so that no two of these diagonals intersect inside the $n$-gon and all the vertices of $n$-gon that are endpoints of diagonals used in dividing the $n$-gon are endpoints of even number of such diagonals.

I found that convex hexagon and nonagon satisfied the conditions,

I think $n$ will probable be multiples of 3 but don't know how to prove.

• You may find that a triangle works too. Maybe call them hexagons and nonagons, that's their usual names... – boboquack Sep 18 '17 at 10:40
• I think even it works fine for a pentagon, where by drawing two diagonals as said, we can see 5 - 2 = 3 triangles resulting. – Mea Culpa Nay Sep 18 '17 at 10:45
• @ Mea Culpa Nay. Pentagon doesn't work because there are 2 vertices not being endpoints of even number of diagonals. – Dan Sep 18 '17 at 11:02
• Please do not vote to close this question, it is not a textbook math question. It isn't solved by some boring routine, and it only requires basic math knowledge to understand. Welcome to the site, Dan, and thank you for sharing this interesting puzzle! – Mike Earnest Sep 18 '17 at 14:14
• mathopenref.com/polygontriangles.html has a good interpretation of this, but if possible Dan can provide with an image/picture about his/her requirement clearly. – Mea Culpa Nay Sep 18 '17 at 15:05

The number of sides $n$ must be a multiple of 3. We will prove this by showing that the $n-3$ diagonals can be partitioned into disjoint groups of 3 forming triangles, and so $n-3$ is a multiple of 3.

The diagonals form a planar Eulerian graph whose faces are all triangles. Since there are no degree-1 vertices, it has at least one interior face, which must be a triangle. Delete such a face that touches the outside by erasing its 3 edges.

Each vertex lost 0 or 2 edges, so the graph remains Eulerian and also still planar. All faces are still triangles, since any other touching face was lost by being exposed to the exterior. So, the conditions are met to repeat the process until no edges remain. Since 3 edges were removed each time, the number of edges was divisible by 3.

Many other answers have shown how to obtain every $n$ divisible by 3; see any of them for a construction.

• Whee, another dot-to-dot! I loved how we can do paper-cut-outs too, I must suggest this to Rubio. – boboquack Sep 19 '17 at 9:59
• Concerning, As there are $n-3$ diagonals, it suffices to partition them into disjoint triangles. Please explain this statement in more detail. Thanks. – Dan Sep 20 '17 at 3:20
• @Dan I tried phrasing it better. – xnor Sep 20 '17 at 3:52

I thought of a different proof to Gareth's, and since it is very related to a conversation I had with @Rubio in chat, I thought I would post it for fun.

Firstly:

Yes, the answer is a multiple of three (EDIT: I've added the construction at the bottom)

So, first, we will do a:

Dot-to-dot!

Specifically:

First convert the vertices and edges into a graph. Then, since it is connected and each vertex has even degree, we can break it up into a set of loops[1] (actually, we can make sure it's one loop, but we won't use that here).

Then we can do some:

Doodling!

I.e.:

Drawing the closed loops formed by completing the dot to dot. For the purpose of the proof, we will define a doodle to be a set of closed loops (that may self-intersect).

We then can do some:

Mindful colouring!

Since:

Any doodle can be coloured in two colours[2] (i.e. each empty area divided by the lines can be assigned one of two colours), such that we don't have two of the same colour adjacent over an edge. We can choose the colours red and blue, and flip the colours so that the outside is red if necessary.

Now we actually have to do some maths:

Each edge is adjacent to exactly one blue portion. But each blue portion is a triangle, because it is not outside the shape. So the number of edges is a multiple of three, i.e. n+(n-3)=2n-3 is a multiple of three, so 2n is a multiple of three and since 2 and 3 are coprime, n must be a multiple of three.

Proof of [1]:

Choose any vertex, and continue to choose any edge that hasn't already been walked along to walk along until you are stuck. You must be stuck at the original vertex, because that is the only vertex where there have been an even number of edges adjacent to it walked along when you arrive (you left once, each time you visited before then you came in and went out k times and you arrived once, giving 2k+2 edges used for this vertex; for the others you visited k times and arrived once, giving 2k+1 edges used and there must be an edge left to traverse because each vertex has even degree). So that's one loop, and we can remove those edges from the graph and do the same thing over and over again, and this will eventually stop because there are only finitely many edges.

Proof of [2]:

First we'll deal with just one loop. We can shuffle the edges slightly so that there aren't any coincidences like this:

Then we can uncross any crossings: To get a collection of simple loops (loops without crossing), which don't cross each other. Note that we haven't created any free ends, so they must still be loops.
Now for each loop in turn, we can add it to an empty plane of one colour and flip the colours inside.

Then, we can recross: And unshuffle (ignoring the small regions that were created):

So that's one loop done. To add another loop in, we can just XOR the colours, e.g.:

and keep doing this until we have added all the loops in!

Construction (oops!):

We choose a vertex, ignore its two neighbours and then construct triangles for each group of three going round the polygon formed by the chosen vertex and the two outside members of the group of three.

• I like your proof. – Gareth McCaughan Sep 18 '17 at 22:48
• @GarethMcCaughan Thanks! Yours is more rigorous, but I couldn't resist – boboquack Sep 18 '17 at 22:50
• Since each vertex has even degree, can we conclude that each border triangle will not have a common edge ? – Dan Sep 19 '17 at 12:49
• @Dan since each vertex has even degree, we can colour some of the triangles black so that each edge is next to exactly one triangle, so the number of edges must be a multiple of three – boboquack Sep 19 '17 at 23:05

The thing can be done

when $n$ is a multiple of 3 but not otherwise.

Proof, part 1:

Clearly it can be done when $n=3$ (by drawing no diagonals). Suppose it's been done for $n$. We'll turn this configuration into one for $n+3$, as follows. Pick any triangle in the configuration; call it ABC (reading anticlockwise around the polygon); duplicate each vertex so that (still reading anticlockwise) we have AaBbCc; in place of the old edges ABC, have new edges ab,aB, bc,bC, ca,cA. Compared with the old configuration this adds two diagonals to each of a,b,c and none to A,B,C, so the counts are all even.

Proof, part 2:

(Confession: I found the idea here.) Suppose we have triangulated an $n$-gon as required here. Pick any triangle and label its vertices 1,2,3. Now repeatedly pick a triangle with exactly two of its vertices labelled and label the third vertex with the label (from {1,2,3}) not already used in that triangle. We will eventually label all the vertices, and because there are no "interior" vertices it is not possible to arrive at any vertex by two different routes, so all the triangles will have the property that their vertices are labelled 1,2,3 in some order. Now, consider any vertex. Say it's labelled 1; then its neighbours are labelled with 2s and 3s; these alternate because each triangle is {1,2,3}, and the number of neighbours is even because of the even-number-of-diagonals condition; therefore its two "outer" neighbours -- the ones adjoining it along the edges of the original polygon -- have different labels. In other words, any three consecutive vertices of the original polygon are labelled 1,2,3 in some order; the only way to do this is for the labels to go ...,1,2,3,1,2,3,... (in one or the other direction); this requires that the number of vertices be a multiple of 3.

Both Gareth and boboquack's answers are excellent. I wanted to write boboquack's answer in a more streamlined way, filling in some more details.

The problem is solvable iff $n$ is a multiple of $3$. If $n$ is a multiple of $3$, number the vertices 0 to n – 1, and draw the triangles

(0, 2, 4), (0, 5, 7), (0, 8, 10), .... , (0, 3k – 1, 3k + 1), ... (0, n – 4, n – 2).

To see that $n$ must be a multiple of $3$, consider an $n$-gon with a valid triangulation where there are an even number of diagonals at each vertex. First, let's color all the interior triangles white and black so that adjacent triangles are different colors. To do this, color one triangle black, the color its neighbors white, then all of its neighbors black, and so on. The only way this would cause a problem was if there were an odd chain of triangles $T_1,T_2,\dots, T_{2k+1}$ where each was adjacent to the last, and where the last was adjacent to the first. But a little thought shows that there cannot be any chain of triangles which loops back to itself, so this cannot happen.

Once this coloring is achieved, I claim that all triangles on the border are the same color. This is because any two border triangles which meet at the same vertex will have an even number of diagonals between them, and each diagonal causes a color change. Going around the border, all border triangles are the same.

Finally, we finish as boboquack did. Suppose the border triangles are black. Every exterior edge and interior diagonal is adjacent to exactly one black triangle, so the number of such edges is a multiple of $3$. Therefore, $n+(n-3)=2n-3$ is a multiple of $3$, so $2n$ is a multiple of $3$, so $n$ is as well.

• Your answer helps us understand boboquack's solution easily. Thank you very much ! – Dan Sep 20 '17 at 3:00