Graph Theory & Combinatorics
The question is as follows:
What is the maximum number of points of intersection between the diagonals of a convex octagon
(8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two
points in its interior lies wholly in the interior of the polygon. Only points of intersection between diagonals
that lie in the interior of the octagon are to be considered for this problem.
The answer, given, is 70.
I cannot find the logic. Help me please!!
Re: Graph Theory & Combinatorics
Each 2-diagonal (joining vertices two steps distant along the perimeter of the octagon) must intersect with 2 others of its kind, plus two 3-diagonals and one 4-diagonal, all emanating from the vertex between on the perimeter.
There are 8 such 2-diagonals, so multiply the previous numbers by 8, except for the intersections of 2-diagonals with their own kind: that number only by 4.
Each 3-diagonal must intersect with two 2-diagonals (but these are already counted), plus four 3-diagonals and both 4-diagonals, all emanating from the two vertices between on the perimeter.
There are 8 such 3-diagonals, so multiply accordingly.
That leaves intersections with 4-diagonals that are not already counted, which is those with their own kind. Each must intersect all 3 others.