Let $G$ be a graph of order $n$ in which there exist no three vertices $u,v$ and $w$ such that $uv, vw$ and $wu$ are all edges in $G.$ Show that $n \geq \Delta(G)+\delta(G).$
May I know if my proof is correct? Thank you.
Let $v \in G$ such that $\text{deg}(v)= \Delta(G)=k.$ Let $v_1,...v_k$ be the vertices incident to $v$.
By the assumption in the problem, there will not be any edge between $v_i$ and $v_j,(i,j=1,...,k).$
For each $v_i (i=1,..,k),\ \text{deg}(v_i) \leq 1+(n-1-k)=n-k$ since $v_i$ could be incident to the $n-1-k$ vertices not incident to $v$. Hence, $\delta(G) \leq n-k$ and $\Delta(G)+\delta(G) \leq k+n-k=n$
Yes, this is a correct well-written proof.
You could marginally simplify the final paragraph by saying:-
Each $v_i$ can only be joined to one of $n-k$ vertices and so $\delta(G)\le n-k$. Therefore $\Delta(G)+\delta(G) \leq n$.