Problem 9.8. On a plane, 36 points are marked, no three of which lie on the same line. Some pairs of marked points are connected by segments such that no more than 3 segments emanate from each marked point.

What is the maximum number of different closed 4-segment broken lines that can result?

The vertices of the broken line can only be the marked points, and the segments can only be the drawn segments. It does not matter where the broken line starts or how it is oriented: for example, if for some 4 marked points \( A, B, C, D \) the segments \( AB, BC, CD, DA \) are drawn, then \( ABCD, BCDA, CDAB, DABC, ADCB, BADC, CBAD, DCBA \) are considered the same broken line.
# Answer: 54.

Solution. First, let's prove that there are no more than 54 broken lines.

Consider a "tick" structure, consisting of three points $A, B$, and $C$, as well as two segments $AB$ and $AC$ (the segment $BC$ may or may not be present; point $A$ will be called the vertex of the tick). Since from $B$ and $C$ no more than two segments can extend, each tick can be contained in no more than two 4-segment broken lines (Fig. 5a). Furthermore, point $A$ can be the vertex of no more than three ticks, so it can be part of no more than six 4-segment broken lines.

![](https://cdn.mathpix.com/cropped/2024_05_06_f585fb32d0f8951822d4g-8.jpg?height=256&width=304&top_left_y=1309&top_left_x=292)

(a)

![](https://cdn.mathpix.com/cropped/2024_05_06_f585fb32d0f8951822d4g-8.jpg?height=234&width=307&top_left_y=1326&top_left_x=856)

(b)

Fig. 5: Solution to problem 9.8

Now let's estimate the number of broken lines. There are 36 points in total, and each point can be part of no more than 6 broken lines, with each broken line involving exactly 4 points. Therefore, the number of broken lines is no more than $36 \cdot 6 / 4 = 54$.

Now let's prove that there could be exactly 54 broken lines.

Describe a construction consisting of 6 points: $A_1, A_2, A_3, B_1, B_2, B_3$ (Fig. 5b). Connect these points with segments such that for all $i, j \in \{1, 2, 3\}$, point $A_i$ is connected to point $B_j$ (thus, from each point, exactly 3 segments extend). Then any pair of vertices $A_{i_1}, A_{i_2}$ together with any pair of vertices $B_{j_1}, B_{j_2}$ will form a 4-segment broken line. Thus, there will be exactly 9 broken lines. To construct the example required in the problem, it is sufficient to consider 6 such constructions, all points of which are distinct.