Nineteenth IMAR Mathematical Competition

Consider the obvious geometric plane graph associated with a generic $n$-line configuration in a plane (no two lines are parallel and no three are concurrent). This graph has exactly $\binom{n}{2} = \frac{1}{2}n(n-1)$ vertices, exactly $e = n^2$ edges and exactly $f = \frac{1}{2}n(n+1)+1$ faces.
Let $f_k$ be the number of $k$-edge faces (faces with exactly $k$ edges), so $f = \sum_{k=2}^{n} f_k$ (no face has more than $n$ edges). Fix an integer $m$ in the range 4 through $n$, to write
$$\begin{align*} 2n^2 = 2e &= \sum_{k=2}^{n} k f_k = \sum_{k=2}^{m-1} k f_k + \sum_{k=m}^{n} k f_k \ge \sum_{k=2}^{m-1} k f_k + m \sum_{k=m}^{n} f_k \\ &= \sum_{k=2}^{m-1} k f_k + m \left( f - \sum_{k=2}^{m-1} f_k \right) = \sum_{k=2}^{m-1} (k-m) f_k + mf, \end{align*}$$
so
$$2n^2 \geq \sum_{k=2}^{m-1} (k-m)f_k + \frac{1}{2}m(n^2+n+2),$$
wherefrom
$$\sum_{k=2}^{m-1} (m-k)f_k \geq \frac{1}{2}m(n^2+n+2) - 2n^2 = \frac{1}{2}((m-4)n^2 + mn + 2m).$$
Next, write $f_k = b_k + u_k$, where $b_k$ and $u_k$ are the numbers of bounded and unbounded $k$-faces, respectively. Thus, $b_k$ is the number of $k$-gons. Clearly, $b_2 = 0$ and $\sum_{k=2}^{n} u_k = 2n$, so
$$\begin{align*} \sum_{k=2}^{m-1} (m-k)f_k &= \sum_{k=3}^{m-1} (m-k)b_k + \sum_{k=2}^{m-1} (m-k)u_k \le \\ &\le \sum_{k=3}^{m-1} (m-k)b_k + (m-2) \sum_{k=3}^{m-1} u_k \le \\ &\le \sum_{k=3}^{m-1} (m-k)b_k + (m-2) \sum_{k=2}^{n} u_k = \sum_{k=3}^{m-1} (m-k)b_k + 2(m-2)n. \end{align*}$$
Consequently,
$$\begin{align*} \sum_{k=3}^{m-1} (m-k)b_k &\ge \sum_{k=2}^{m-1} (m-k)f_k - 2(m-2)n \ge \\ &\ge \frac{1}{2}((m-4)n^2 + mn + 2m) - 2(m-2)n = \\ &= \frac{1}{2}((m-4)n^2 - (3m-8)n + 2m) = \frac{1}{2}((m-4)n - m)(n-2), \end{align*}$$
so
$$\max(b_3, \dots, b_{m-1}) \ge \frac{1}{2} \cdot \frac{((m-4)n - m)(n-2)}{(m-3) + \dots + 1} = \frac{((m-4)n - m)(n-2)}{(m-3)(m-2)}.$$
The coefficient of $n^2$ in the lower bound is maximized at $m=5$ and $m=6$, so
$$\max(b_3, b_4) \ge \frac{1}{6}(n-5)(n-2) \quad \text{and} \quad \max(b_3, b_4, b_5) \ge \frac{1}{6}(n-3)(n-2).$$