in Graph Theory recategorized by
3 votes
3 votes

A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent vertices, and is contained in the interior of the polygon (except for its points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such polygon with $n$ vertices, a certain number (say $k$) of  non-crossing diagonals were drawn to cut up the inside of the polygon into regions, each of which was a quadrilateral. how many diagonals were drawn, that is, what is $k$?

  1. cannot be determined from the information given
  2. $\frac{n}{2}-2$
  3. $\frac{n}{4}-1$
  4. $n-4$
  5. $n^2 - 9.5 n +22$
in Graph Theory recategorized by

3 Answers

3 votes
3 votes

We have drawn k diagonals on a n-sided polygon.

Now, total edges = n(sides)+k(diagonals) = n+k

For each diagonal we draw, one extra region will be formed. Initially, there are 2 regions (entire region inside polygon and the external region)

total regions = k+2

Now, using the law, sum of degrees of all regions = 2*no of edges.

Here, r-1 regions will have degree of 4 (all the regions formed inside polygon) and the external region has degree (n+k) as it is bounded by (n) edges (sides of the polygon).

So, 4*(r-1)+(n)*1=2*e
Option B is correct

edited by

1 comment

A n-gon will be partinioned in the above manner. Let us number the partitions as 1, ..., i, i+1, ..., n/2. It can be seen that there are going to be n/2 such partitions for n-gon. As logically adding one more partition and two sides on top and bottom one can form another quadrilateral attached to the previous n-gon and in the process making a (n+3)-gon.

But there will always be two sides of the polygons acting as partitions on the extreme ends, i.e., the 1st and the (n/2)th partitions in this image. They are the non-diagonal partitions. So the number of diagonal partitions is (n/2-2).

So B is correct.

1 vote
1 vote
Each region is quadrilateral i.e bounded by 4 sides.


So we can write 4r<=2e


A n-gon has n sides. Also K diagonals are drawn, so total sides will be n+k.




Therefore, 4(k+2)<=2(n+k)

=> k<=n-4
0 votes
0 votes

Way to approach :- Let suppose our polygon contains 'n' vertices. Then we can observe that minimum number of vertices must be 5 , to have at least on such diagonal that cut the polygon into at least one quadrilateral region.

Now to find total number of such diagonals , we can follow this approach

match Vn to V3 , match Vn-1 to V4 , match Vn-2 to V5 ......match Vn-(x-3) to Vx

When we follow this approach we will come to know that when our 'n' is even there would be 4 vertices that can't be map in that manner and when 'n' is odd there would be 3 such vertices.

so that's the overall approach

attaching image.


Related questions