Jump to content

User:Esequia/Teorema de Mantel

From Wikipedia, the free encyclopedia

Mantel's Theorem is a particular case of Turán's Theorem for .

Result

[edit]

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

Mantel's Theorem If and has n vertices, then

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 , this is true since each vertex in G is connected with at most one of u or v. Then,

Finally,

Where follow from hypothesis and -1 comes to the fact that edge uv has being counted twice in .