Show that if a graph $G$ of order $n$ is triangle-free, then $$n \ge \delta(G) + \Delta(G).$$
What I have tried so far is as follows. I wish to show $n > \Delta(G) + \delta(G)$ implies there is a triangle. Choose a vertex $u$ with degree $\Delta(G)$. Consider the neighborhood $N(u)$ of $u$. There are $n - \Delta(G) - 1$ vertices is $V(G)\setminus N(u)$. Choose a vertex $v$ in $V(G)\setminus N(u)$. It has at least $\delta(G)$ neighbors. $\delta(G) > n - \Delta(G) $ . Thus $u$ and $v$ share two vertices in their neighborhood forming a cycle of length $4$.
$\endgroup$ 12 Answers
$\begingroup$We may assume that $\Delta(G)\gt0$. Choose a vertex $u$ with $\deg u=\Delta(G)$ and choose a vertex $v\in N(u)$. Since $G$ is triangle-free, $N(u)$ and $N(v)$ are disjoint subsets of $V(G)$, so we have$$n=|V(G)|\ge|N(u)|+|N(v)|\ge\Delta(G)+\delta(G).$$
$\endgroup$ $\begingroup$Suppose that $$n<\delta(G)+\Delta(G).$$ We want to prove by contrapositivity that $G$ has a triangle.
Let $u$ be a vertex of maximum degree in $G$, and $v$ one of its neighbours. We must show that there exists a common neighbour $w$ of $u$ and $v$, and so $u$, $v$, and $w$ form a triangle in $G$.
To show this, let $N_x$ denote the set of neighbours of a vertex $x$ of $G$. Then, $$|N_u\cap N_v|=|N_u|+|N_v|-|N_u\cup N_v|\geq \Delta(G)+\delta(G)-n>0,$$since $|N_u|=\Delta(G)$, $|N_v|\geq \delta(G)$, and $|N_u\cup N_v|\leq n$. Thus, $N_u\cap N_v$ is non-empty, and the claim follows.
$\endgroup$
