Prove that the graph is connected 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.

 A: Proof:
If each degree is at least that, then each component has at least one vertex and $\frac{n-1}{2}$ others, so at least $\frac{n-1}{2}+1=\frac{n+1}{2}$ vertices. Two components would have at least twice as many vertices, which is n+1, more than the graph has.
(I realize this is the same as David's, but I don't like unnecessary variables so I feel it's still worth posting.)
Edit: Different wording, appropriate for the OP's stated terminology/knowledge:
Alternative proof:
Take any two vertices. Each has at least $\frac{n-1}{2}$ neighbors. If there were no path between our two vertices, then the two neighborhoods must be separate and we'd have at least $2\cdot(1+\frac{n-1}{2})=n+1$ vertices, more than the graph has.
A: suppose the graph has at least two distinct connected components, $C_1$ and $C_2$. denote by $c_1,c_2$ two vertices, one in each component.
$C_1$ has the vertex $c_1$ and at least $\frac{n-1}2$ other vertices, one for each edge incident to $c_1$, a total of at least $\frac{n+1}2$. likewise $C_2$ must have at least $\frac{n+1}2$ vertices.
the graph must therefore have at least
$$
\frac{n+1}2 + \frac{n+1}2 = n+1
$$
 vertices, contradicting the assumption
A: I think this can be done by induction on the number of vertices: this is trivially true for $n=1,2$. Assume true for $n=k$, i.e., every graph on $k$ vertices where each vertex has degree $\geq (k-1)/2 ; k>2 $ ,is path-connected.
Now consider a graph $S_{k+1}$ on $k+1 $ vertices. Isolate any subgraph $S_k$ with $k$ vertices, and define $v_{k+1}:= S_{k+1}-S_k$, i.e., $v_{k+1}$ is just the vertex of $S_k$ thatis not in $S_{k+1}$ (EDIT : ignore edges out of/into $v_{k+1})$ . By induction, $S_k$ is path-connected. We know $Deg(v_{k+1}) \geq (k+1-1)/2=k/2 $. But now we just need
$Deg(v_{k+1}) \geq 1 $ . Now join $v_{k+1}$ with any $v_j ; j \neq k+1$, which gives you, by path-connectedness of $S_k$ a path between $v_{k+1}$ and $v_j$;
$k+1 \neq j$.  
EDIT   Alternatively, consider a path-connected graph on $k-1$ vertices, with $Deg(v_j) \geq (k-1)/2$ . Throw in a new vertex $v_{k+1}$ and draw  and edge between $v_{k+1}$ and every other edge, and you have a path-connected graph with $Deg(v_j)=(k-1)/2+1 =(k+1)/2 \geq k/2$
A: 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$
