Courses
Courses for Kids
Free study material
Offline Centres
More

Mantel's Theorem

ffImage
Last updated date: 28th Feb 2024
Total views: 161.1k
Views today: 1.61k
hightlight icon
highlight icon
highlight icon
share icon
copy icon

An Introduction to 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


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.

Competitive Exams after 12th Science

FAQs on Mantel's Theorem

1. What is a triangle-free graph?

A triangle-free graph is an undirected graph in the mathematical field of graph theory where no three vertices form a triangle of edges. Triangle-free graphs can also be described as having a clique number of two or less, a girth of four, the absence of an induced 3-cycle, or locally independent graphs.

Balanced complete bipartite graphs are triangle-free graphs with the greatest number of edges per vertex. Many triangle-free graphs, such as any cycle graph Cn for odd n > 3, are not bipartite.

2. What does a complete bipartite graph mean?

A complete bipartite graph is a particular type of bipartite graph in the study of graph theory where each vertex in the first set is connected to each vertex in the second set. Every potential edge that might connect vertices in distinct subsets is present in a full bipartite graph, which has vertices that can be partitioned into V1 and V2 subsets such that no edge has both of its endpoints in a single subset. It is a bipartite graph (V1, V2, E), which means that there is an edge in E for each pair of vertices v1 and v2.

3. What is Turan's Theorem, and how does it relate to or contrast with Mantel's Theorem?

A graph has few edges if there aren't any cliques greater than three, according to Mantel's Theorem. If a graph doesn't have any cliques larger than r+1, Turan's Theorem states that it contains some but few edges.


Furthermore, both theorems are tight, indicating that there are graphs with precisely this many edges. This would be a fully bipartite network for Mantel's Theorem, with the left part having n/2 vertices, the right half having n/2 vertices, and the graph having all edges connecting these two sections. This will be exactly n square/4 edges, according to Mantel's Theorem.