# Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$). Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges of $m$ convex sub-polygons of $P$ which do not share any edges.

($Q$ is a sub-polygon of $P$ if all vertices of $Q$ are vertices of $P$).

This question was proposed at a Chinese contest and maybe it's a known result in graph theory.

For $n=5$, for example, it's not hard to see that $m(5)=3$. If $P:=P_{1}P_{2}P_{3}P_{4}P_{5}$, $m(5)=3$ can be achieved by 3 convex sub-polygons: $P_{1}P_{2}P_{4}P_{5}$; $P_{1}P_{3}P_{4}$; $P_{2}P_{3}P_{5}$. I also found that $m(7) \leq 6$, but I couldn't go further.

Any suggestion would be appreciated. Thanks in advance.

• If it is a contest problem, maybe you may ask organizers or participants of the contest? – Fedor Petrov Jul 18 '15 at 15:42
• @FedorPetrov Unfortunately this one took place in the early 90s. I'm not aware of any organizer/participant of this contest. – jack Jul 18 '15 at 15:58
• Must $m\lt n$ hold, or is $m\le n$ also possible? – Manfred Weis Jul 19 '15 at 7:45
• @ManfredWeis There are no restrictions on $m$, except it has to be the smallest possible. So $m \leq n$ is also possible. – jack Jul 19 '15 at 14:57
• I deleted my comment because I thought diagonals were also not to be shared. However, I thought a sub-polygon of a convex polygon was also convex (I guess vertex order matters?). There may still be a design interpretation, but my original one does not quite capture the problem. Gerhard "Thinks This Still Isn't Geometry" Paseman, 2015.07.19 – Gerhard Paseman Jul 19 '15 at 23:15

Here's a lower bound that heynongman and I worked out. (This was previously posted with equality, but there was a flaw in the argument.) This is assuming that the diagonals (as well as the edges) of $P$ are not to be shared among the sub-polygons.

Suppose that the edges and diagonals of $P$ can be covered by $m$ convex sub-polygons $Q_1$, $Q_2$, ..., $Q_m$, having $a_1$, $a_2$, ..., $a_m$ edges, respectively. We want to cover $n\choose2$ edges and diagonals in all, so

$$a_1+a_2+\cdots+a_m={n\choose2}.\tag{1}$$

We define the cost $c(e)$ of an edge $e$ of $P$ (around the perimeter) to be 0, and the cost $c(e)$ of a diagonal $e$ to be the smallest number of intermediate vertices of $P$ in a path along the perimeter of $P$ from one endpoint to the other. For example, for $n=7$ and $P=P_1P_2P_3P_4P_5P_6P_7$, the cost of the diagonal $P_2P_6$ is 2 (because the shortest path around the perimeter between the endpoints is $P_6P_7P_1P_2$, which has two intermediate vertices). Intuitively, the cost of a diagonal is the minimum number of vertices of $P$ that must be "skipped" by a sub-polygon $Q_i$ that uses that diagonal, traversing the vertices of $Q_i$ clockwise.

The maximum cost of a diagonal is $(n-3)/2$. At each vertex, because $n$ is odd, there are exactly two diagonals of each cost from 1 to $(n-3)/2$, so the total cost of diagonals incident upon a given vertex is $2\sum_{i=1}^{(n-3)/2}i=(n-1)(n-3)/4$. If we sum over all vertices, we count the cost of each diagonal twice, so the sum of the costs of all edges and diagonals of $P$ is

$$\sum_{e\in P}c(e)={n\over2}\left[(n-1)(n-3)\over4\right].$$

Now, for any sub-polygon $Q_i$, every vertex of $P$ is either a vertex of $Q_i$ or is "skipped" by $Q_i$. The total cost of the edges of $Q_i$, $\sum_{e\in Q_i}c(e)$, is a lower bound on the number $n-a_i$ of "skipped" vertices, which is to say that $n-a_i\ge\sum_{e\in Q_i}c(e)$. (Our previous post claimed that $\sum_{e\in Q_i}c(e)=n-a_i$, but this is not necessarily true, because a sub-polygon may lie entirely in "one half" of $P$.) Therefore,

$$(n-a_1)+(n-a_2)+\cdots+(n-a_m)\ge\sum_{i=1}^m\sum_{e\in Q_i}c(e)=\sum_{e\in P}c(e)={n(n-1)(n-3)\over8}.\tag{2}$$

Adding (1) and (2), we get

$$mn\ge{n\choose2}+{n(n-1)(n-3)\over8}={n(n-1)(n+1)\over8},$$

so $m\ge(n-1)(n+1)/8$.

This lower bound gives $m(5)\ge3$, $m(7)\ge6$, and $m(9)\ge10$. We have constructions that meet this bound for $n=5,7,9$, but we don't have a general construction.

I think the following construction realizes the lower bound in Brian's answer. Let $n=2k+1$ and label the first $2k$ vertices with $\mathbb{Z}_{2k}=\{0,\ldots,2k-1\}$ and the last vertex with $\infty$. First we take all the $(n-1)(n-3)/8=2k(k-1)/4$ 4-gons of the form $(i,\,i+j,\,i+k,\,i+k+j)$ with $i\in\{0,\ldots,2k-1\}$ and $j\in\{1,\ldots,k-1\}$. That covers everything not involving $\infty$ except the "long" diagonals $(i,i+k)$, so we add $(n-1)/2=k$ triangles $(i,i+k,\infty)$ for $i\in\{0,\ldots,k-1\}$.