Graph theory - inequality

Question

I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory.

We consider G = (V,E) a graph with n a natural number (n is the number of vertices), that doesn't contain any triangles. (so the vertices don't form any triangle inside the graph)

the problem is about solving : |E|≤ (n^2) / 4

all I know is that {u,v}∈E : deg(u)+deg(v) ≤ n (I don't know if it is relevant to the problem though...)

Answer 1

Recall by the Cauchy-Schwarz inequality that if $\vec a, \vec b \in \mathbb R^n$, then $\vec a \cdot \vec b \leq \|\vec a\| \|\vec b\|$, which can be rewritten as: $$ \left(\sum_{i=1}^n a_ib_i \right)^2 \leq \left(\sum_{i=1}^n a_i^2 \right)\left(\sum_{i=1}^n b_i^2 \right) $$ Now let $V = \{v_1, \ldots, v_n\}$ and take $a_i = 1$ and $b_i = \deg v_i$. Then it follows that: \begin{align*} |E| &= \frac{(2|E|)^2}{4|E|} \\ &= \frac{\left(\sum_{i=1}^n 1\deg v_i \right)^2}{4|E|} &\text{by the handshaking lemma}\\ &\leq \frac{\left(\sum_{i=1}^n 1^2 \right)\left(\sum_{i=1}^n (\deg v_i)^2 \right)}{4|E|} &\text{by the Cauchy-Schwarz inequality}\\ &= \frac{n\sum_{i=1}^n\sum_{v_iv_j \in E} (\deg v_i) }{4|E|} \\ &= \frac{n\sum_{v_iv_j \in E} (\deg v_i + \deg v_j)}{4|E|} \\ &\leq \frac{n(n|E|)}{4|E|} &\text{since $G$ is triangle-free}\\ &= \frac{n^2}{4} \end{align*} as desired. $~~\blacksquare$

Answer 2

Here's another approach:

Let $v$ be a vertex of maximum degree in $G=(V,E)$. Then $$\mathrm{deg}(v) \geq \text{ave. deg.} = \dfrac{2|E|}{n} \geq \dfrac{n}{2}$$ since $|E| \leq n^2/4$.

Let $S$ be the set of neighbors of $v$. Let $H$ be the complete bipartite graph with vertex bipartition formed by $S$ and $V \setminus S$.

We observe:

• $H$ has at most $n^2/4$ edges,

• in going from $G$ to $H$,

  • the degree of $v$ remains the same,
  • the degrees of the vertices in $S$ are no smaller in $H$ than in $G$, and
  • the degrees of the vertices in $V \setminus ( S \cup \{v\} )$ are now all equal to $|S|=\mathrm{deg}(v)$, which is the maximum degree in $G$,

  so $H$ has no fewer edges than $G$, and

• $H$ is triangle free.

Hence $|E| \leq n^2/4$.