Polygon and its diagonals.

Question

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.

Answer 1

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.

Answer 2

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