Prove that if the graph G does not contain K3 as a subgraph, then | V (G) | ≥ δ (G) + Δ (G) I need help with the following proof:
Prove that if the graph G does not contain K3 as a subgraph, then |V (G)| ≥ δ (G) + Δ (G).
K3 ... is a complete graph with three vertices
|V (G)| ... is the number of vertices of the graph G
δ (G) ... is the minimum degree of the graph G
Δ (G) ... is the maximum degree of the graph G
I have the idea that:
a) It is a tree, so at most δ = 1 and Δ = n-1
n ≥ 1 + n - 1
b) We add one edge - it will contain K3, but still n vertices, at most δ = 2 and Δ = n-1
n ≥ 2 + n - 1 does not apply
c) We add two edges - either it contains two K3 and it still has n vertices, or we add a vertex and it contains K4
Two K3 - at most δ = 3 and Δ = n-1, so similarly to the previous case, this does not apply
K4 - now of vertices n + 1, at most δ = 2 and Δ = n-1
n + 1 ≥ 2 + n - 1 applies
In order for the graph to contain the cycle Kn, n ≥ 3, we must always add n-3 vertices to the tree. However, only in the case of K3 we do not have to add any vertex, so if the graph contains such a subgraph, then |V (G)| ≥ δ (G) + Δ (G) cannot apply.
Would someone please advise me how to rephrase this proof correctly, or how to go a different way ? Thank you for any advice.
 A: Here is a proof using the Inclusion–exclusion principle (https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle):
If $\Delta(G)+\delta(G) > |V|$, let $m$ be the vertex st. $d(m) = \Delta(G)$. Then, for every $v \in V$, $d(m) + d(v) > |V|$, hence $N(m) \cap N(v) \neq \varnothing$. $N(v)$ denotes the neighborhood of $v$, which is a set of vertices that are adjacent to $v$. Since $G$ is $K_3$-free, there is no edge connecting $m$ and $v$. By the arbitrariness of $v$, we have $d(m) = 0$ and $\Delta(G)+\delta(G) = 0$, contradiction.
A: This is the same as Muses_China's proof but presented more straightforwardly.
$N(v)$ is the neighborhood of the vertex $v$, the set of all vertices adjacent to $v$. Since $G$ is a simple graph, $|N(v)|=d(v)$. If $\Delta(G)=0$ there is nothing to prove, so we assume that $\Delta(G)\ge1$.
Choose a vertex $v$ with $d(v)=\Delta(G)$ and choose $w\in N(v)$. Note that $N(v)\cap N(w)=\varnothing$, as otherwise $G$ would contain a $K_3$. Hence
$$|V(G)|\ge|N(v)\cup N(w)|=|N(v)|+|N(w)|=d(v)+d(w)=\Delta(G)+d(w)\ge\Delta(G)+\delta(G).$$
