| Version current |
Version 2 |
| \PMlinkescapeword{weight} |
Let's consider a graph $G$ with $n$ vertices and no triangles and find a charaterization for this kind of graphs which make them distinct from those graphs which have $n$ vertices and at least one triangle.Let a vertex $v_i$ $i=1,2,..,n$ has his own weight $w_i$ such that $\Sigma w_i=1$ . |
| \PMlinkescapeword{push} |
Let $S$=$\Sigma w_iw_j$ for any ($i$,$j$) in $E(G)$. Now,take two vertices $h$ ,$k$ not joined let $x$ the total weight of the neighbors of $k$ so $y$ is for $k$ and let's assume $x>=y$.If we take a little portion of weight from the vertex k and we put this in the weight of h then ,this shifting won't decrease S, so S would be maximal when all the weight is over a $K_2$ ,that is a complete subgraph made up of two vertices.Therefore,since $S=vw$ and $v+w=1$ at last $w=v=1/2$ and $S<=1/4$.The theorem is proven considering all the weights equal to $1/n$.In fact in this case $S=1/n^2 |E(G)|$ and $|E(G)|<=n^2/4$. |
| \PMlinkescapeword{support} |
|
|
|
| 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 |
|
| \[ |
|
| 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}{|V(G)|}$ on each vertex. The total weight of this function is |
|
| \[ |
|
| W(c_0) = \sum_{uv\in E(G)} \frac{1}{|V(G)|}\cdot\frac{1}{|V(G)|}=\frac{|E(G)|}{|V(G)|^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 |
|
| \begin{equation*} |
|
| \sum_{uw\in E(G)} c(w) \ge \sum_{vw\in E(G)} c(w).\tag{*} |
|
| \end{equation*} |
|
| Now we push the function off $v$. To do this, define a function $c^*\colon V(G)\to\mathbb{R}_+$ by |
|
| \[ |
|
| 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^*$, |
|
| \begin{align*} |
|
| W(c^*) |
|
| &= \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) \\ |
|
| &= \sum_{uw\in E(G)} [c(u) + c(v)]\cdot c(w) + 0 + \sum_{wz\in E(G)} c(w)\cdot c(z) \\ |
|
| &= \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) \\ |
|
| &= W(c). |
|
| \end{align*} |
|
| 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 |
|
| \[ |
|
| \frac{1}{4}=W(c)\ge W(c_0)=\frac{|E(G)|}{|V(G)|^2}, |
|
| \] |
|
| which gives us the desired inequality: $|E(G)|\le\frac{|V(G)|^2}{4}$. |
|
