PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
[parent] alternate proof of Mantel's theorem (Proof)

Let $G$ be a triangle-free graph of order $n$ For each edge $xy$ of $G$ we consider the neighbourhoods $\Gamma(x)$ and $\Gamma(y)$ of $G$ Since $G$ is triangle-free, these are disjoint.

This is only possible if the sum of the degrees of $x$ and $y$ is less than or equal to $n$ So for each edge $xy$ we get the inequality

$$ \delta(x)+\delta(y)\leq n $$

Summing these inequalities for all edges of $G$ gives us $$ \Sigma_{x\in V(G)} (\delta(x))^2 \leq n |E(G)| $$

(The left hand side is a sum of $\delta(x)$ where each edge incident with $x$ contributes one term and their are $\delta(x)$ such edges.)

Since $\Sigma_{x\in V(G)} \delta(x) = 2 |E(G)|$ we get $4 |E(G)|^2 = (\Sigma_{x\in V(G)} \delta(x))^2 $ and applying the Cauchy-Schwarz inequality gives $4 |E(G)|^2 \leq n \Sigma_{x\in V(G)} (\delta(x))^2 \leq n^2 |E(G)|$

So we conclude that for a triangle-free graph $G$ $$|E(G)|\leq\frac{n^2}{4} $$




"alternate proof of Mantel's theorem" is owned by lieven.
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: Cauchy-Schwarz inequality, term, incident, left hand side, inequality, degrees, sum, disjoint, edge, order, graph

This is version 2 of alternate proof of Mantel's theorem, born on 2008-03-25, modified 2008-03-25.
Object id is 10440, canonical name is AlternateProofOfMantelsTheorem.
Accessed 689 times total.

Classification:
AMS MSC05C69 (Combinatorics :: Graph theory :: Dominating sets, independent sets, cliques)
 05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)