Maximum Edges in a Triangle-Free Graph

Problem Statement

A triangle in a simple undirected graph is a set of three distinct vertices {u, v, w} such that edges (u, v), (v, w), and (w, u) all exist. A graph is said to be triangle-free if it contains no triangles.

Given an integer n representing the number of vertices labeled from 0 to n - 1, determine:

1. The maximum possible number of edges in a triangle-free simple graph with n vertices.
2. An edge list representing any valid triangle-free graph that achieves this maximum.

Implement the function max_triangle_free_graph(n) which returns a tuple (max_edges, edge_list).

• max_edges: An integer denoting the maximum number of edges.
• edge_list: A list of tuples (u, v) representing the undirected edges where `0 tuple[int, list[tuple[int, int]]]: pass

## Constraints

- `1 <= n <= 1000`
- The graph must be simple: no self-loops and no multi-edges.
- Time complexity should be `O(n^2)` to construct the edges, with the edge count computed in `O(1)`.
- Space complexity should be `O(n^2)` to store the output edges.

## Examples

### Example 1
```python
Input: n = 4
Output: (4, [(0, 2), (0, 3), (1, 2), (1, 3)])
Explanation:
A complete bipartite graph K_{2,2} with parts {0, 1} and {2, 3} has 2 * 2 = 4 edges and contains no triangles.

Example 2

Input: n = 5
Output: (6, [(0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4)])
Explanation:
Partitioning vertices into parts of size 2 and 3 gives K_{2,3}, which has 2 * 3 = 6 edges.
No simple graph on 5 vertices can have 7 edges without forming a triangle.

Edge Cases

• n = 1: No edges can be drawn; return (0, []).
• n = 2: At most 1 edge (0, 1) can be drawn; return (1, [(0, 1)]).
• n = 3: Maximum edges is 2 (a path of length 2). Adding a 3rd edge forms a triangle.