Example 2 In a simple graph with eight vertices, what is the maximum number of edges in a graph without a quadrilateral?

The maximum number of edges in a graph without a quadrilateral in a simple graph with eight vertices is what?
Let the maximum number of edges in all simple graphs with $n(n \geqslant 4)$ vertices that do not contain a quadrilateral be denoted as $S_{n}$.
It is easy to see that $S_{4}=4$.
Now consider the case when $n=5$.
In a simple graph with five vertices and six edges, since the sum of the degrees of all vertices is 12, there must be a vertex with a degree no greater than 2.

If there is a vertex with a degree of 1, removing that vertex reduces the problem to a graph with four vertices and five edges, which must contain a quadrilateral.

Therefore, we only need to consider the case where each vertex has a degree of at least 2.
(1) If the graph has a vertex $A$ with a degree of 3, the edges from $A$ are $A B, A C, A D$. For another vertex $E$, since its degree is at least 2, it must be adjacent to at least two of the vertices $B, C, D$, thus forming a quadrilateral.
(2) If the graph has a vertex $P$ with a degree of 4, the four edges from $P$ are $P A, P B, P C, P D$. Since the degrees of $A, B, C, D$ are all at least 2, and the total degree sum is 12, the degrees of $A, B, C, D$ must all be 2, and in this case, there is indeed no quadrilateral.

When $n=5$, if a graph has at least seven edges, there must be a vertex with a degree no greater than 2. Removing that vertex (and the edges it emits) reduces the problem to a graph with four vertices and at least five edges. According to the previous discussion, this graph must contain a quadrilateral.

Therefore, $S_{5}=6$, and the only 5-vertex graph with six edges and no quadrilateral is as shown in Figure 1.
Furthermore, $S_{6}=7$.
In a graph with six vertices and eight edges, there is always a vertex with a degree no greater than 2, denoted as $P$.

If $d(P)=1$, removing vertex $P$ reduces the problem to a graph with five vertices and seven edges. According to the previous discussion, this graph must contain a quadrilateral.

If $d(P)=2$, removing vertex $P$ reduces the problem to a graph with five vertices and six edges, and in this case, the graph without a quadrilateral has only one form (all other cases contain a quadrilateral).

Based on this, adding back the removed vertex and two edges, no matter how they are added, a quadrilateral will always be formed, meaning that a graph with six vertices and eight edges must contain a quadrilateral.

Additionally, a graph with six vertices and seven edges without a quadrilateral exists, as shown in Figure 2.
Therefore, $S_{6}=7$. Furthermore, $S_{7}=9$.
In a graph with seven vertices and ten edges, there is always a vertex with a degree no greater than 2. Removing that vertex reduces the problem to a graph with six vertices and at least eight edges.
According to $S_{6}=7$, this graph must contain a quadrilateral.
Thus, a graph with seven vertices and ten edges must contain a quadrilateral.
For a graph with seven vertices and nine edges, a graph without a quadrilateral exists, as shown in Figure 3.
Therefore, $S_{7}=9$.
Next, we prove: $S_{8}=11$.
First, a graph with eight vertices and eleven edges without a quadrilateral exists, as shown in Figure 4.

Second, a graph with eight vertices and twelve edges must contain a quadrilateral.
Proof by contradiction.
If there exists such a graph without a quadrilateral, if there is a vertex with a degree no greater than 2, removing that vertex reduces the problem to a graph with seven vertices and at least ten edges.
According to the previous discussion, this graph must contain a quadrilateral, which contradicts the assumption.
Therefore, each vertex has a degree of at least 3.
Since a graph with eight vertices and twelve edges has a total degree sum of 24, each vertex must have a degree of exactly 3, and in this case, the graph must contain a triangle (in fact, if there is no triangle, take any vertex $A$, and the three edges from $A$ are $A B, A C, A D$, then there can be no edges between $B, C, D$, and the two other vertices adjacent to $B$ must be among the remaining vertices, denoted as
$$
\bar{E}=\left\{E_{1}, E_{2}, E_{3}, E_{4}\right\},
$$

i.e., the two other vertices adjacent to $B$ are in $\bar{E}$. The same applies to vertices $C$ and $D$, indicating that there are six edges between the sets $\{B, C, D\}$ and $\bar{E}$. Therefore, there must be a vertex in $\bar{E}$, for example, $E_{1}$, that emits at least two edges to the set $\{B, C, D\}$, say $E_{1} B, E_{1} C$, thus forming a quadrilateral by vertices $A, B, E_{1}, C$, which is a contradiction).

Let $\triangle A B C$ be a triangle in the graph. Since each vertex has a degree of exactly 3, each of $A, B, C$ emits one edge outside the triangle. Removing $\triangle A B C$ removes six edges, leaving a graph with five vertices and six edges. If this graph has no quadrilateral, according to the previous discussion, it has only one form.

However, in this case, there is a vertex with a degree of 4, which contradicts the fact that "each vertex has a degree of exactly 3" in the graph. Therefore, the assumption is false. Hence, a graph with eight vertices and twelve edges must contain a quadrilateral.