User:Esequia/Teorema de Mantel

Mantel's Theorem is a particular case of Turán's Theorem for $r=3$ .

Result edit

The following was established by Mantel in 1907. It's one of earliest results in Extremal graph theory

Mantel's Theorem If

G\nsupseteq C_{3}

and has

n

vertices, then

e(G)\leq {\frac {n^{2}}{4}}.

Where $e(G)$ is the number of edges on $G$ . In other words the theorem provide a bound on the number of edges of a graph that has no triangle. It is easy to see that bigger graph with no triangles is the complete bipartite graph.

Demonstração edit

For $n$ =1 and $n$ =2 the result is trivial. Suppose that results holds for $n-1$ and let $G$ be the graph with $n$ vertex. Let $u$ and $v$ be adjacent vertices in $G$ , then $d(u)+d(v)\leq n$ , this is true since each vertex in $G$ is connected with at most one of $u$ or $v$ . Then,

e(G)=e(G-\{u,v\})+d(u)+d(v)-1

e(G-\{u,v\})+d(u)+d(v)-1\leq {\frac {(n-2)^{2}}{4}}+n-1

Finally,

e(G)\leq {\frac {n^{2}}{4}}

Where $e(G-\{u,v\})$ follow from hypothesis and -1 comes to the fact that edge $uv$ has being counted twice in $d(u)+d(v)$ .