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



Dividing the edges and diagonals of a polygon among disjoint sub-polygons
Here's a lower bound that [heynongman](https://mathoverflow.net/users/76060/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.


