I was wondering if someone can help me understand how prove that this graph is connected.
Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph is connected.
So far I know that about connected graphs:
An undirected graph is called connected if there is a path between
every pair of distinct vertices of the graph
The distance between two vertices in a graph is the length of
the shortest path between them.
The diameter of a graph is the distance between the two vertices
that are farthest apart.
Best Answer
Call the $n$-vertex graph $G$. Choose any two vertices $u,v \in V(G)$. We want to find a $(u,v)$-path. Now if $u = v$ or $uv \in E(G)$, then we are done. So we may assume that $u \neq v$ and $uv \notin E(G)$. We will prove the stronger claim that there is some path of the form $u \to w \to v$ for some $w \in V(G)$.
Consider the neighbourhoods of each endpoint: \begin{align*} A &= \{a \in V(G) \mid ua \in E(G)\} \\ B &= \{b \in V(G) \mid vb \in E(G)\} \end{align*} It suffices to show that these neighbourhoods overlap (if they do, then we can just pick any $w \in A \cap B$ and we are done). Indeed, observe that: \begin{align*} |A \cap B| &= |A| + |B| - |A \cup B| \\ &= \deg(u) + \deg(v) - |A \cup B| \\ &\geq \frac{n - 1}{2} + \frac{n - 1}{2} - (n - 2) \\ &= 1 \end{align*} Hence, we conclude that $A\cap B \neq \varnothing$, as desired. $~~\blacksquare$