Maximum Edges in a Triangle-Free Graph

You are given `n` labeled vertices arranged as a polygon. You may draw any undirected edge between two distinct vertices, including polygon sides and diagonals. The drawing may contain crossings; only graph adjacency matters. Implement: ```text max_triangle_free_edges(n: int) -> int ``` Return the largest number of edges a simple graph on these `n` vertices can have while containing no three vertices that are pairwise connected. ### Constraints - `1 <= n <= 100_000_000` - No self-loops or duplicate edges are allowed. - The result must be computed without constructing the graph. ### Clarifications - A triangle is a set of three distinct vertices with all three connecting edges present. - Edge crossings do not create vertices and do not affect whether a triangle exists. - Compute the answer as `floor(n / 2) * ceil(n / 2)`, not as `n * n / 4`. Under the stated bound, that product is at most `2_500_000_000_000_000`, so it is an exact integer in JavaScript `Number` as well as Java and C++ 64-bit integer types. ```hint Split the vertices Consider how many cross-group edges are possible when every edge joins two different groups. ``` ### Examples ```text Input: n = 4 Output: 4 Input: n = 5 Output: 6 ``` ### Evaluation Focus - Derive the extremal edge count for both even and odd `n`. - Explain why the construction is triangle-free and why no denser graph can be triangle-free. - Use constant extra space and constant-time arithmetic without an overflowing or inexact intermediate. ### Extension Describe one graph construction that achieves the returned maximum.