Example 5 Given $n$ points $A_{1}, A_{2}, \cdots, A_{n}(n \geqslant 3)$ in the plane, no three of which are collinear. By selecting $k$ pairs of points, determine $k$ lines (i.e., draw a line through each pair of the $k$ selected pairs), such that these $k$ lines do not form a triangle with all three vertices being given points. Find the maximum value of $k$.
(1996, Shanghai High School Mathematics Competition)
Solution: Let the line passing through the point pair $A_{1}, A_{2}$ be $l$, then $A_{1}, A_{2}$ cannot both connect to any of the remaining $n-2$ points, meaning the lines passing through $A_{1}$ or $A_{2}$ are at most $n-1$ (including $l$).

Similarly, for the $n-2$ points $A_{3}, A_{4}, \cdots, A_{n}$, the lines passing through $A_{3}$ or $A_{4}$ are at most $n-3$, ….. Therefore,
$$
\begin{array}{l}
k \leqslant(n-1)+(n-3)+\cdots \\
=\left\{\begin{array}{ll}
\frac{n^{2}}{4} & (n \text { is even }), \\
\frac{n^{2}-1}{4} & (n \text { is odd }) .
\end{array}\right.
\end{array}
$$

On the other hand, divide the $n$ points into two groups: when $n$ is even, each group has $\frac{n}{2}$ points; when $n$ is odd, one group has $\frac{n-1}{2}$ points, and the other group has $\frac{n+1}{2}$ points. Then, connect each point in the first group with any point in the second group to form $\frac{n^{2}}{4}$ or $\frac{n^{2}-1}{4}$ lines, which clearly do not form a triangle with three vertices all being given points.
Thus, the maximum value of $k$ is
$$
k_{\max }=\left\{\begin{array}{ll}
\frac{n^{2}}{4} & (n \text { is even }), \\
\frac{n^{2}-1}{4} & (n \text { is odd }) .
\end{array}\right.
$$