Mantel's Theorem

We will examine numerous crucial aspects of the Mantel Theorem. Mantel's theorem, established by Willem Mantel in 1907, is the basis of extremal graph theory and implies that any graph on n vertices without a triangle contains at most \[\dfrac{{{n^{\;2}}}}{4}\] edges. By splitting the collection of n vertices into two sets of size \[\left[ {\dfrac{n}{2}} \right]\] and \[\left[ {\dfrac{n}{2}} \right]\], one may build the entire bipartite graph between them, making this the best feasible scenario. There are \[\left[ {\dfrac{{{n^2}}}{4}} \right]\] edges and no triangles in this graph. Let's understand the basics by stating and proving the Mantel theorem.

What is Mantel's Theorem?

If there are no triangles in a graph G on n vertices, then the number of edges is at most \[\dfrac{{{n^{\;2}}}}{4}\].

Triangle Free Graph

Mantel's Theorem Proof

Consider G to have m edges. Let x and y represent two G vertices that are connected by an edge. We can see that d(x) + d(y) ≤ n if d(v) is the degree of a vertex v. This is since each vertex in graph G is only connected to one of x and y. Now observe that

\[\mathop \sum \limits_x {d^{\;2\;}}\left( x \right)\; = \mathop \sum \limits_{\;xy \in E\;} \left( {d\left( x \right)\; + \;d\left( y \right)} \right)\; \le \;mn\]

On the other hand, the Cauchy–Schwarz inequality suggests that because \[\mathop \sum \limits_x \;d\left( x \right)\; = \;2m,\]

\[\mathop \sum \limits_x \;{d^{\;2\;}}\left( x \right)\; \ge \;\dfrac{{{{\left( {\;\mathop \sum \limits_x \;d\left( x \right)} \right)}^2}\;}}{n}\; \ge \dfrac{{\;4{m^2}\;\;}}{n}\]

Therefore,

\[\dfrac{{4{m^2}}}{n} \le mn\]

and the result follows.

Applications of Mantel's Theorem

• This theorem can be applied to determine how many edges an N-vertex graph can have while still being free of triangles.

• Mantel's theorem graph theory is the basis for the external graph theory.

Mantel’s Theorem Examples

1. Show that there are \[\left[ {\dfrac{{{n^2}}}{4}} \right]\] edges in the n-vertex complete balanced bipartite graph. It implies that some graphs can reach the bound in Mantel's theorem.

Ans: A triangle subgraph does not exist in the n-vertex complete bipartite graph with class sizes \[\left[ {\dfrac{n}{2}} \right]\] and \[\left[ {\dfrac{n}{2}} \right]\], and the graph has exactly \[\left[ {\dfrac{n}{2}} \right]\left[ {\dfrac{n}{2}} \right]\; = \left[ {\dfrac{{{n^2}}}{4}} \right]\] edges. There are no graphs without triangles that have more edges than what is stated by Mantel's theorem.

2. Using an induction method that eliminates two nearby vertices, demonstrate Mantel's theorem.

Ans: Assume n > 2 and that the theorem's statement is true for smaller graphs because if n = 1, 2, we are finished. Let \[xy\;\]be an edge of graph G, which has n vertices and no triangles, and let G be the graph. Since the graph G - xy has n - 2 vertices and is manifestly triangle-free, it can be inferred that it has no more than \[\left[ {\dfrac{{{{\left( {n - 2} \right)}^2}}}{4}} \right]\] edges. At most n edges incident on the edge \(xy\) (otherwise, there is a triangle). Thus, G can only have

\[1\; + \;\left( {n - \;2} \right)\; + \dfrac{{\;{{\left( {n - \;2} \right)}^2}}}{4} = \dfrac{{{n^2}}}{4}\] edges.

3. If G is a triangle-free graph, then there are no common neighbours for neighbouring vertices. Therefore, we have \[d\left( x \right)\; + \;d\left( y \right)\; \le \;n\] n for an edge \[xy\;\] (remember to count the edge \[xy\;\] twice). Use it in the following equation to support your case that it is correct.

\[\mathop \sum \limits_{x \in V\left( G \right)} d{\left( x \right)^2}\; = \mathop \sum \limits_{xy \in E\left( G \right)} \left( {d\left( x \right)d\left( y \right)} \right)\;\] to obtain Mantel's theorem's proof.

Ans: First, we get

\[\mathop \sum \limits_{x \in V\left( G \right)} d{\left( x \right)^2}\; = \mathop \sum \limits_{xy \in E\left( G \right)} \left( {d\left( x \right)d\left( y \right)} \right)\; \le n\left| {E\left( G \right)} \right|\]

Utilising Cauchy-Schwarz,

\[\dfrac{1}{n}{\left( {\mathop \sum \limits_{x \in V\left( G \right)} d\left( x \right)} \right)^2}\; \le \mathop \sum \limits_{x \in V\left( G \right)} d{\left( x \right)^2}\]

The LHS is \[\dfrac{{\;1}}{n}(2|E\left( G \right){|^2}\;\] according to the Handshaking lemma. Thus,

\[\dfrac{{\;1}}{n}(2|E\left( G \right){|^2}\; \le n\left| {E\left( G \right)} \right|\]

Now, the theorem can be obtained by solving for |E(G)|.

Conclusion

In this article, we have discussed about Mantel's theorem and its proof. With Mantel's theorem, we can evaluate how many edges an N-vertex graph can have in total without having any triangles (which means there should not be any three edges A, B, and C in the graph such that A is connected to B, B is connected to C, and C is connected to A). The graph is not allowed to have many edges or a self-loop. To obtain a graph without triangles, it is necessary to remove almost half of the edges.

Important Points From the Theorem

• Only if m = \[\dfrac{{{n^{\;2}}}}{4}\] is a graph G maximally triangle-free with regard to edges.

• It is necessary to eliminate roughly half of the edges in order to produce a graph without triangles.

• If a graph contains no cliques greater than three, then it satisfies Mantel's Theorem that it has few edges.