PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of Mantel's theorem (Proof)

Let $ G$ be a triangle-free graph. We may assume that $ G$ has at least three vertices and at least one edge; otherwise, there is nothing to prove. Consider the set $ P$ of all functions $ c\colon V(G)\to\mathbb{R}_+$ such that $ \sum_{v\in V(G)} c(v)=1$. Define the total weight $ W(c)$ of such a function by

$\displaystyle W(c) = \sum_{uv\in E(G)} c(u)\cdot c(v). $
By declaring that $ c\le c^*$ if and only if $ W(c)\le W(c^*)$ we make $ P$ into a poset.

Consider the function $ c_0\in P$ which takes the constant value $ \frac{1}{\vert V(G)\vert}$ on each vertex. The total weight of this function is

$\displaystyle W(c_0) = \sum_{uv\in E(G)} \frac{1}{\vert V(G)\vert}\cdot\frac{1}{\vert V(G)\vert}=\frac{\vert E(G)\vert}{\vert V(G)\vert^2}, $
which is positive because $ G$ has an edge. So if $ c\ge c_0$ in $ P$, then $ c$ has support on an induced subgraph of $ G$ with at least one edge.

We claim that a maximal element of $ P$ above $ c_0$ is supported on a copy of $ K_2$ inside $ G$. To see this, suppose $ c\ge c_0$ in $ P$. If $ c$ has support on a subgraph larger than $ K_2$, then there are nonadjacent vertices $ u$ and $ v$ such that $ c(u)$ and $ c(v)$ are both positive. Without loss of generality, suppose that

$\displaystyle \sum_{uw\in E(G)} c(w) \ge \sum_{vw\in E(G)} c(w).$ (*)

Now we push the function off $ v$. To do this, define a function $ c^*\colon V(G)\to\mathbb{R}_+$ by
$\displaystyle c^*(w) = \begin{cases} c(u)+c(v) & w=u \ 0 & w=v \ c(w) & \text{otherwise.} \end{cases}$
Observe that $ \sum_{w\in V(G)} c^*(w) = 1$, so $ c^*$ is still in the poset $ P$. Furthermore, by inequality (*) and the definition of $ c^*$,
$\displaystyle W(c^*)$ $\displaystyle = \sum_{uw\in E(G)} c^*(u)\cdot c^*(w) + \sum_{vw\in E(G)} c^*(v)\cdot c^*(w) + \sum_{wz\in E(G)} c^*(w)\cdot c^*(z)$    
  $\displaystyle = \sum_{uw\in E(G)} [c(u) + c(v)]\cdot c(w) + 0 + \sum_{wz\in E(G)} c(w)\cdot c(z)$    
  $\displaystyle = \sum_{uw\in E(G)} c(u) \cdot c(w) + \sum_{vw} c(v)\cdot c(w) + \sum_{wz\in E(G)} c(w) \cdot c(z)$    
  $\displaystyle = W(c).$    

Thus $ c^*\ge c$ in $ G$ and is supported on one less vertex than $ c$ is. So let $ c$ be a maximal element of $ P$ above $ c_0$. We have just seen that $ c$ must be supported on adjacent vertices $ u$ and $ v$. The weight $ W(c)$ is just $ c(u)\cdot c(v)$; since $ c(u)+c(v)=1$ and $ c$ has maximal weight, it must be that $ c(u)=c(v)=\frac{1}{2}$. Hence
$\displaystyle \frac{1}{4}=W(c)\ge W(c_0)=\frac{\vert E(G)\vert}{\vert V(G)\vert^2}, $
which gives us the desired inequality: $ \vert E(G)\vert\le\frac{\vert V(G)\vert^2}{4}$.



Anyone with an account can edit this entry. Please help improve it!

"proof of Mantel's theorem" is owned by mps. [ full author list (2) | owner history (1) ]
(view preamble)

View style:


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

Cross-references: adjacent vertices, inequality, without loss of generality, subgraph, maximal element, induced subgraph, positive, vertex, poset, functions, edge, vertices, graph

This is version 3 of proof of Mantel's theorem, born on 2002-09-14, modified 2006-11-25.
Object id is 3455, canonical name is ProofOfMantelsTheorem.
Accessed 2319 times total.

Classification:
AMS MSC: 05C69 (Combinatorics :: Graph theory :: Dominating sets, independent sets, cliques)
 05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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