4.21 In a simple graph with 8 vertices, what is the maximum number of edges in a graph without a quadrilateral? (A simple graph is one where no vertex is connected to itself, and there is at most one edge between any two vertices.)

将上面的文本翻译成英文，请保留源文本的换行和格式，直接输出翻译结果。
[Solution 1] In the graph shown in the right figure, there are 8 vertices and 11 edges, and there is no quadrilateral. From this, we know that the maximum number of edges sought is no less than 11.

Next, we will prove that if the graph has 12 edges, then it must contain a quadrilateral.
First, we point out two obvious facts:
(i) Let $A \neq B$ be two vertices. If point $A$ is connected to points $C_{1}, \cdots, C_{k}$, and $B$ is connected to at least two points in $\left\{C_{1}, \cdots, C_{k}\right\}$, then the graph must contain a quadrilateral.
(ii) If 4 points are connected by 5 edges, then the graph must contain a quadrilateral.
Suppose there is a graph with 8 vertices and 12 edges that does not contain a quadrilateral, and point $A$ is one of the vertices with the most edges.
(1) Suppose $A$ has $s \geqslant 5$ edges, and the set of vertices connected to $A$ is $S$, and the set of all vertices except $A$ and $S$ is $T$. Then, by (i) and (ii), the number of edges between points in $S$ is at most $\left[\frac{s}{2}\right]$, the number of edges between points in $T$ is at most $C_{T}^{2}$, and the number of edges between $S$ and $T$ is at most $|T|$. Therefore, the total number of edges in the graph is at most
$$
\left.\left.s+\left[\frac{s}{2}\right]+|T|+C\right\}_{T} \left\lvert\,=7+\left[\frac{s}{2}\right]+C\right.\right\}_{T} \mid .
$$

When $s \geqslant 5$, the number of edges is less than 12, which is a contradiction.
(2) Point $A$ has exactly 4 edges: $A A_{j}(j=1,2,3,4)$. Suppose the other 3 points are $B_{1}, B_{2}, B_{3}$. Then, the set $\left\{A_{1}, A_{2}, A_{3}, A_{4}\right\}$ has at most 2 edges, and the set $\left\{B_{1}, B_{2}, B_{3}\right\}$ has at most 3 edges, and there are at most 3 edges between these two sets. Since the graph has 12 edges, the number of edges in these three categories must be exactly 2, 3, and 3. Without loss of generality, assume the 3 edges between the sets are $A_{j} B_{j}(j=1,2,3)$. Since the first set has 2 edges and they do not share a common endpoint, there is an edge between $\left\{A_{1}, A_{2}, A_{3}\right\}$, say $A_{1} A_{2}$. Thus, $A_{1} A_{2} B_{2} B_{1}$ forms a quadrilateral, which is a contradiction.
(3) Point $A$ has exactly 3 edges, and thus each point has 3 edges. Suppose points $A$ and $B$ are not connected, and the 3 edges from each are $A A_{j}, B B_{j}(j=1,2,3)$. Then, by (i), the sets $\left\{A_{1}, A_{2}, A_{3}\right\}$ and $\left\{B_{1}, B_{2}, B_{3}\right\}$ have at most 1 common point.

If they have no common point, then each set of 3 points has at most 1 edge, and there are at most 3 edges between the two sets. Thus, the total number of edges in the graph is at most 11, which is a contradiction.

If the two sets have exactly 1 common point, then consider the 8th point $C$. By the pigeonhole principle, 2 of the 3 edges from $C$ must go to the same set of 3 points, which leads to a quadrilateral, which is a contradiction.

In summary, we have proven that in a graph with 8 vertices and 12 edges, there must be a quadrilateral. Therefore, the maximum number of edges sought is 11.
[Solution 2] The graph shown in the right figure has 8 vertices and 11 edges, but no quadrilateral, so the maximum number of edges sought is no less than 11.

To prove that in a graph with 8 vertices and 12 edges, there must be a quadrilateral, we first prove the following lemma:

Lemma If a graph with 5 vertices and 6 edges has no quadrilateral, then the graph must be two triangles sharing exactly one vertex.
[Proof] Since the sum of the degrees of 5 vertices is 12, there must be a vertex with a degree no greater than 2. If there is a vertex $A$ with a degree no greater than 1, then the 4 remaining vertices have 5 edges, and by (ii), there must be a quadrilateral, which is a contradiction. Therefore, each vertex has a degree of at least 2.

If the graph has a vertex $A$ with a degree of 3, let the 3 edges from it be $A B$, $A C$, $A D$. At this time, the 5th vertex $E$ must connect to at least 2 of $\{B, C, D\}$, thus there must be a quadrilateral, which is a contradiction.

In summary, the degrees of the 5 vertices in the graph can only be 4, 2, 2, 2, 2, i.e., the graph is two triangles sharing exactly one vertex. The lemma is proven.

Suppose in a graph with 8 vertices and 12 edges, there is no quadrilateral. At this time, the sum of the degrees of 8 vertices is 24, so there must be a vertex with a degree no greater than 3.
(1) If there is a vertex $A$ with a degree no greater than 2, then after removing $A$, the remaining 7 vertices have at least 10 edges. The sum of the degrees of 7 vertices is 20, so there must be a vertex $B$ with a degree no greater than 2. Then, the 6 remaining vertices have at least 8 edges. The sum of the degrees of 6 vertices is 16, so there must be a vertex $C$ with a degree no greater than 2. Then, the 5 remaining vertices have at least 6 edges. Thus, we have proven that there must be a subgraph with 5 vertices and at least 6 edges.
(2) If each vertex has a degree of at least 3, then each vertex has a degree of 3. Let the 3 edges from vertex $A$ be $A B, A C, A D$. Each of $B, C, D$ connects to 2 other vertices, say $\{E, F\},\{G, H\},\{I, J\}$. If two of these 3 pairs have a common vertex, then there must be a quadrilateral, so the three pairs do not intersect. But since there are only 8 vertices, there must be an edge between $\{B, C, D\}$. Without loss of generality, assume the edge $B C$ exists, then $\triangle A B C$ exists, and when these 3 vertices are removed, the remaining 5 vertices still have 6 edges.

From (1) and (2), we know that there must be a subgraph with 5 vertices and at least 6 edges. If this subgraph has 7 edges, then when the vertex with the smallest degree is removed, the remaining 4 vertices have at least 5 edges, thus there must be a quadrilateral, which is a contradiction. Therefore, this subgraph with 5 vertices has exactly 6 edges. By the lemma, it is two triangles sharing exactly one vertex (see the right figure).

If one of $A, B, C$ connects to 2 of the remaining 5 vertices, then there must be a quadrilateral, which contradicts the assumption. Therefore, each vertex can connect to at most 1 of the remaining 5 vertices. If 2 of the 3 edges from $A, B, C$ to the remaining 5 vertices have a common endpoint, then there must be a quadrilateral. Therefore, these 3 edges do not share a common endpoint. By the pigeonhole principle, 2 of the 3 endpoints in the remaining 5 vertices must be in the same triangle, thus leading to a quadrilateral, which is a contradiction.