Example 4 Given ten points in space, where no four points lie on the same plane. Connect some of the points with line segments. If the resulting figure contains no triangles and no spatial quadrilaterals, determine the maximum number of line segments that can be drawn.
Solution
Let the ten points be . Using these ten points as vertices and the line segments connecting them as edges, we obtain a simple graph of order 10. Let the degree of point be . Then the total number of edges in graph is .
In graph , we call the figure formed by two line segments sharing a common endpoint an angle. Thus, there are different angles.
By the given condition, for any angle in graph , and are not adjacent. For any two angles and , we have
.
Thus, the complement graph of has at least edges.
Therefore, the total number of edges satisfies
which implies .
Also, , so
A specific construction is shown in Figure 1.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.