Connected graph and degrees minimun and maximun

Question

Let G=(V,E) be a graph of order n such that $\delta(G) + \Delta(G) \ge n - 1$. Prove that the graph is connected. Prove that $diam(G) \le 4$.

How would I prove this? thanks

Answer 1

Let $v$ be the node in $G$ that provides $\Delta(G)$, i.e $d(v)=\Delta(G)$. We will show that every node $u$ in $G$ is connected to $v$ and therefore $G$ is connected. By the definition of $\delta$ we have $$d(u)\geq \delta(G)$$ and therefore $$d(u)+d(v) \geq \delta(G)+ \Delta(G) \geq n-1$$ if there's an edge $(u,v)$ than we done, else from pigeon hole prinicple we get that there's a node $w$ which have edges from both $u,v$ , and therefore $u,v$ are connected.

This is also shows that for every tow vertices $x,y$ theres a path from $x$ to $v$ from size $\leq 2$ and same from $v$ to $y$ and therefore we have a path from $x$ to $y$ which is $\leq 4$ which shows exactly $$diam(G)\leq 4$$

Answer 2

Only a partial answer (proof of the connectedness)

If $G$ is not connected, it must have two connecting components with $u$ and $v$ vertices. WLOG, assume $u\le v$

Then the minimum degree is at most $u-1$, the maximum degree at most $v-1$. So $\delta(G)+\Delta(G)\le u-1+v-1=n-2<n-1$, which is a contradiction.