Consider a graph $G$ of $n$ vertices with minimum degree of a node $\delta (G)$ and maximum degree of a node $\Delta (G)$, prove that if $\delta(G) + \Delta (G) \ge n-1$, then $G$ is connected and diameter $\le 4$.
Definitions:
- Diameter of a graph is the maximum distance between any two pair of vertices.
- Distance of two vertices is the minimum path value between those two nodes.
My not-so-sure solution: Let $u$ and $v$ be the vertices with maximum and minimum degree repectively. If $u$ and $v$ are adjacent then according to conditions, there can be diameter of atmost 2. If the vertices are not adjacent then it can be proved that there must be a common vertex adjacent to both $u$ and $v$. If this is possible then we can have any path length of atmost value 4, which goes through this common vertex.
Firstly you prove that $\delta$ and $\Delta$ have a common neighbor. Then you prove that the graph must be connected, otherwise in the other part of the graph, the vertices have smaller degree than $\delta$. To prove the diameter part, you use a degree of any vertex, which is bigger than $\delta$ thus has a common neighbor with $\Delta$, for the same reason $\delta$ had. And that will be the end of the proof.