So there is a N sided polygon, and some given number of lines, K that we can use as diagonals to connect its vertices. For simplicity, if we view the polygon as a cyclic graph with N vertices, the goal is to use all K lines to connect its diagonals and minimize the number of incoming edges (or degree) of all vertices of the graph as much as possible by distributing every K over the vertices optimally, and finally get the maximum of degrees of all the vertices as the answer to the problem. In short, you have to try minimizing the degree of individual vertices, then the result is the maximum of the set of degrees of all vertices at that configuration.

for example,

if, N = 6 and K = 2,

the maximum degree of the graph after using all K lines to connect vertices( 6 in this case, one diagonal connecting two each), is 3.

Explanation, lets number the vertices of the hexagon here as 0, 1, 2, ...5. Now, we have to use all the K (=3) lines here as diagonals, so we can connect,

vertex 0 to vertex 2, vertex 1 to vertex 4, vertex 3 to vertex 5.

We have used up all the K lines as we were asked and the maximum of all the degrees we get is 3

( 2 + 1), where 2 edges are of adjacent vertices of that vertex and remaining one is the diagonal to the opposite vertex. ( there can be another configurations too like 0 to 3, 1 to 5 and 2 to 4, the output is same). In this case, every vertex will have same degree, i.e. 3, hence the max is 3.

Apparently, the output is same of same hexagon and with K = 2, because the maximum of degrees of all the vertices is still 3.

A few more examples, for, N = 6 and K = 8, result is 5,

for N = 5 and K = 4, result is 4.

I have been trying to establish some algebraic relation between N and K by simulating different situations but i have not been able to observe any pattern till now.

Any ideas?

P.S. : For clarification, the K cannot exceed $n*(n-3)/2$ , because that is the max. number of diagonals a polygon can have.

also, you can't overwrite already existing diagonals.

  • $\begingroup$ Tell me if this is not what you are saying: when $K=0$ the result is $2$ as you seem to be counting the outer edges of the polygon anyway; when $0 \lt K \le \frac n2$ the result is $3$. Is there any reason to suppose this pattern does not continue, so when $\frac n2 \lt K \le n$ the result is $4$, and when $n \lt K \le \frac{3n}{2}$ the result is $5$, and in general when $(c-1)\frac{n}{2} \lt K \le c\frac{n}{2}$ the result is $c+2$? $\endgroup$ – Henry Sep 12 '19 at 22:20
  • $\begingroup$ @Henry , try N = 6 , K = 6, according to your simulation result should be 4, but if you try drawing a hexagon on paper, the result is 5, you have to try minimize the degree of individual vertices, then choose maximum one out of them as the result, in case of n,k = 6, 6; 5 of 6 when 5 of 6 lines are used up, the maximum degree is 4, when the 6th line comes, it has to connect to a vertex which already has degree 4. $\endgroup$ – sweetsecret Sep 12 '19 at 22:50
  • 1
    $\begingroup$ sweetsecret: With $N=6,K=6$ you start with a hexagon and can draw a hexagram inside (you end up with every connection except those to opposite vertices) so every vertex is of degree $4$ $\endgroup$ – Henry Sep 13 '19 at 7:53
  • $\begingroup$ @Henry Yes, you are right, the pattern seems to follow this inequality. $\endgroup$ – sweetsecret Sep 13 '19 at 16:23

I'll suppose that $n\geq3$ and $k\leq\frac{n(n-3)}{2}$ as otherwise there are more diagonals to draw than there are possible pairs of vertices to connect. If you allow edges with multiplicity, however, the same argument still holds.

Let $r$ be the remainder of $k$ divided by $n$, so that $k=qn+r$ for some nonnegative integer $q$. As $k\leq\frac{n(n-3)}{2}$ we have $q\leq\tfrac{n-3}{2}$. Label the vertices of the cyclic graph with the elements of the cyclic group $\Bbb{Z}/n\Bbb{Z}$. For each $a\in\Bbb{Z}/n\Bbb{Z}$ and each $b\in\{2,\ldots,q+1\}$ draw a diagonal between $a$ and $a+b$. Note that all these diagonals are distinct because $q\leq\tfrac{n-3}{2}$. Now every vertex has degree $2q+2$, and there are $r<n$ diagonals left to draw:

  1. If $r=0$ then the minimal maximum degree is $2q+2$.
  2. If $0<r\leq\tfrac{n}{2}$ then the minimal maximum degree is $2q+3$.
  3. If $\tfrac{n}{2}<r<n$ then the minimal maximum degree is $2q+4$.

Recall that twice the number of edges is the sum of the vertex degrees, so the average vertex degree is $${2(n+k)\over n}$$ There must then be at least one vertex of degree $$2+\left\lceil{2k\over n}\right\rceil$$ which is the minimum possible.

  • $\begingroup$ Wait, are you saying $2 + \lceil 2k/n \rceil $? $\endgroup$ – sweetsecret Sep 12 '19 at 22:36
  • $\begingroup$ @sweetsecret Yes, thank you. $\endgroup$ – saulspatz Sep 12 '19 at 22:57
  • $\begingroup$ but it is still not working, you have to find the maximum of the set of degrees of all vertices of the polygon. Your solution finds the minimum degree of the set. $\endgroup$ – sweetsecret Sep 12 '19 at 23:05
  • 2
    $\begingroup$ @sweetsecret I thought you wanted to minimize the maximum degree. That's what this does. Try it on your examples. $\endgroup$ – saulspatz Sep 13 '19 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.