0
$\begingroup$

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 Answers 1

2

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

  • 0
    Ah! Mantel's theorem on triangle-free graphs, cited by Bollobás.2012-10-22