Prove connectivity of graph with vertices of degree $\geq \lfloor \frac n2 \rfloor$ Claim: A graph with vertices of degree at least $\lfloor \frac n2 \rfloor$ where $n = $ number of vertices and $n \geq 3$ is connected.
I tried to prove this by contradiction, but I didn't know what to make of the $\lfloor \frac n2 \rfloor$ part.
 A: Assume for a contradiction that the graph is not connected. This means that the vertices can be partitioned into two nonempty sets $X$ and $Y$ so that there are no edges between $X$ and $Y$; namely, choose a vertex $x_0$ and let $X$ be the set of all vertices connected $x_0$ by a path, and let $Y$ be the rest of the vertices.
Now suppose $X$ is the smaller of the two sets. How big can $X$ be? $X$ contains at most half the vertices in the graph, so $|X|\le\frac n2$.  Since $|X|$ is an integer, it follows that $|X|\le\lfloor\frac n2\rfloor$. How big can the degree of a vertex in $X$ be? If $x\in X$ then $x$ is joined only to vertices in $X\setminus\{x\}$, so $x$ has degree $\le\lfloor\frac n2\rfloor-1$, contradicting the assumption that all vertices have degree $\ge\lfloor\frac n2\rfloor$.
This argument does what you asked for, but N.S.'s answer is better because it proves more: your graph is not only connected, it has diameter at most $2$.
A: Let $u, v$ be two vertices. If $uv$ is an edge, that is a path from u to v.
Otherwise, each of $u$ and $v$ is connected to at least $\lfloor \frac n2 \rfloor$ of the remaining $n-2$ vertices.
As $\lfloor \frac n2 \rfloor+\lfloor \frac n2 \rfloor >n-2$, by the pigeon hole principle there exists a vertex $w$ so that $uw$ and $vw$ are edges. Thus $u -w-v$ is  a path from $u$ to $v$. 
