# Proof about Graph with no triangle

For graph G without a triangle(with no triangle) with n vertices and m edges Prove that:

1)$\forall xy \in E , d(x)+d(y) \le n$

2)$(\sum_{v\in_V}^{ }d(v)^2)\le mn$

-

## 1 Answer

HINTS:

1. For each vertex $x$ in $G$ let $N(x)$ be the set of neighbors of $x$, i.e., the vertices $y$ such that $xy$ is an edge of $G$. If $G$ contains no triangles, what can you say about $N(x)\cap N(y)$ when $x$ and $y$ are distinct vertices of $G$? Is that possible if $\deg(x)+\deg(y)>n$?

2. From (1) you know that $\deg(x)+\deg(y)\le n$ for each $xy\in E$. Sum that inequality over $E$: $$\sum_{xy\in E}\Big(\deg(x)+\deg(y)\Big)\le mn\;,\tag{1}$$ since there are $m$ edges. Now rewrite the summation as a sum over vertices instead of edges: for a given vertex $x$, how many times does a $\deg(x)$ term appear in the summation in $(1)$?

-
Ah! Mantel's theorem on triangle-free graphs, cited by Bollobás. – Hendrik Jan Oct 22 '12 at 21:57