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$
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$
HINTS:
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$?
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)$?