partition of convex n-gon with triangles.

Question

A convex $n$-gon is partitioned into $n-2$ triangles with non-intersecting diagonals. For each vertex of the original polygon, odd number of the partitioning triangles share that vertex. Is it possible to prove that $n$ is a multiple of $3$ ?

Answer 1

The triangulated polygon can also be regarded as a planar graph $G$, and then the condition that each vertex has an odd number of triangles incident to it is equivalent to there being an even number of edges from each vertex, i.e. each vertex of $G$ has even degree. There must be vertices of degree $4$ or more, otherwise the graph is a triangle and the result holds.

Now we label the vertices counterclockwise around the boundary of the triangulated polygon as $1,2,3,\cdots n$ where the vertex labelled $1$ has degree at least $4$. So there are already edges of the form $(k,k+1)$ for $1 \le k \le n$ where the vertex labels are mod $n$ (so the edge $(n,n+1)$ is actually the edge $(n,1)$.

the simple case

We first make a (very) simplifying assumption: For each odd $k \le n-2$ there is, besides the edge $(k,k+1),$ another edge $(k,k+2).$ Note that this implies that vertex $k+1$ has degree $2$ since it is a vertex of one of the triangles in the polygon's triangulation. We will be constructing a path in the graph joining the odd numbered vertices, i.e. the path $$(1,3,5,\cdots, r)$$ where $r$ is the largest odd integer at most $n+1.$ We can always go one more step in this construction, since on arriving at a given odd vertex we have only "used up" one of the edges going to it, so there must be another going out besides the one along the boundary of the polygon. This implies also that the degree of each odd numbered vertex is at least $4.$ If $n$ is even, then $r=n+1$ and the path closes, i.e. is a cycle. On the other hand, if $n$ is odd then $r=n$ and the path does not close, and is a path in $G$ joining vertex $1$ to vertex $n$.

To finish the simple case, we first take $n=2k$ even. As noted above, in this case the path $(1,3,\cdots n)$ is actually a cycle. We now delete from $G$ all the even numbered vertices (each of which has degree $2$) along with the edges joining them to their neighbors, forming a new graph $G'.$ We've deleted $k$ vertices, so that $G'$ has the remaining $k$ vertices. It also holds that each vertex of $G'$ has even degree; at each vertex of $G$ two edges have been removed, so the degree count at that vertex has decreased by $2$. Since as noted that degree was initially at least $4$ we see that each vertex of $G'$ has even degree, and also $G'$ is the triangulation of a polygon (vertices $1,3,5,...,n-1$). By induction then, $G'$ has say $k=3t$ vertices, so that $n=2\cdot 3t$ is a multiple of $3$ as desired, in this $n$ even case.

Now if $n=2k+1$ is odd, the path is $1,3,5,...,n$ and after deletion of the even numbered vertices as before we have a graph $G'$ all of whose vertices besides the two ends $1,n$ of the path have even degree. Note that $k$ vertices have been deleted, and so there are now $k+1$ vertices in $G'.$ The next step is to adjoin a new vertex $N$ to $G'$ which connects to the two vertices $1$ and $n$. These are adjacent in the graph $G'$ with odd degree; with the new $N$ inserted, the resulting graph $G''$ now has all vertices with even degree, and is a triangulated polygon. It follows that $(k+1)+1=k+2=3r$ say, so that $k=3r-2$, and then since $n=2k+1$ we finally get $n=2(3r-2)+1=6r-3,$ a multiple of $3$ as desired for the case of odd $n$.

The "non simple" case

Here we have some vertex $V$ of degree at least $4$, for which there is not an edge connecting $V$ to $V+2$. We need now to be specific about the next choice. Consider a moving ray based at $V$ which initially passes through the next vertex $V+1$ and rotates toward the inside of the polygon. There will then be a first vertex $W$ it passes which is the other end of an edge from $V$. In this "nonsimple case" we're assuming that there are two or more vertices located between $V$ and $W$ going around the boundary of $G$ counterclockwise. We will now split $G$ by cutting it via the line segment $VW$. This makes two subgraphs $A,B$ where $A$ is the half containing $V+1.$ For each of $A,B$ we regard the edge $(V,W)$ as one of the edges of the subgraph (and the two vertices $V,W$ are also viewed as being in each subgraph).

Consider graph $A$. Each of its vertices other than $V,W$ retain their degrees from $V$ and so have even degree. Vertex $V$ (as a vertex of $A$) has degree $2$ by construction. Therefore the degree of $W$ in $A$ is even also, since the number of vertices of odd degree in a graph is even. We see that $A$ satisfies the hypotheses of even degree vertices in a triangulated polygon, and also the number of vertices in $A$ is smaller than that in $G$ (the degree at $V$ being at least $4$). Conclusion: The number of vertices in $A$ is a multiple of $3,$ say $3w.$ This means the number of vertices between $V$ and $W$ along the polygon $G$ is $3w-2$, and also note here $w \ge 2$ since we have more than one vertex between $V$ and $W$ along the boundary of $G$.

Now consider graph $B$. It has $n-(3w-2)$ vertices, and all of its vertices have even degree in $B$ except for vertices $V,W$ each of which has odd degree in $B$. Then (similar to the $n$ odd subcase of the "simple case" above) we can insert another vertex $N$ and edges from it to $V$ and $W$ to make a graph $B'$ which now has $n-(3w-2)+1=n-3w+3$ vertices. Note that since $w\ge 2$ we have that $B'$ has fewer vertices than does $G$, and that $B'$ satisfies the hypotesis of being a triangulated polygon with all vertices having even degree. We can then conclude that $n-3w+3$ is divisible by $3,$ and so $n$ is also a multiple of $3. This finishes the "non simple" case.

I've looked at this for some time and it seems OK to me now. (I initially had some attempts at an answer which were not on the right track.) I'd appreciate any feedback, maybe improvements or even if someone notices a gap that needs filling.