\documentclass[11pt]{article}
\usepackage{amsmath}
\newcommand{\diam}{\mathop{\mathrm{diam}}}
\newtheorem{theorem}{Theorem}
\newenvironment{proofhelper}[1]%
{\begin{trivlist}\item\textbf{Proof.}#1\quad\ignorespaces}%
{\hfill\rule{1ex}{1ex}\end{trivlist}}
\newenvironment{proof}%
{\begin{proofhelper}{}}%
{\end{proofhelper}}
\title{More Detailed Proof of\\Chartrand and Zhang's Theorem 2.4}
\author{MCS-236}
\date{2011-09-29}
\begin{document}
\maketitle
\begin{theorem}
Let $G$ be a graph of order $n$. If
\[ \deg u + \deg v \geq n - 1 \]
for each pair of nonadjacent vertices $u$ and $v$, then $G$ is connected and $\diam(G) \leq 2$.
\end{theorem}
\begin{proof}
If two vertices, $x$ and $y$, are adjacent, then it is immediate that there is a path between them of length~$1$. All that remains is to show that for each nonadjacent pair of vertices $u$ and $v$ as described in the premise of the theorem, there exists a length~$2$ path from $u$ to $v$.
In other words, we will show that $u$ and $v$ have at least one neighbor in common. Having restated the theorem's conclusion in terms of neighbors, we will do the same with the premise.
The degree of a vertex is equal to its number of neighbors. Thus we can restate the premise as
\[\lvert N(u)\rvert + \lvert N(v)\rvert \geq n-1.\]
Notice that the left-hand side of the inequality is now expressed as the sum of two sets' cardinalities. There is a general rule that applies in that situation; for any two sets, the sum of the cardinalities is the same as the cardinality of the union plus the cardinality of the intersection. (The union accounts for all elements that are in either of the sets, but to count a second time the elements that are in both sets, you need to add in the size of the intersection.)\pagebreak
Based on this general rule, we can rewrite our inequality as
\begin{equation}\label{union-intersection}
\lvert N(u) \cup N(v) \rvert + \lvert N(u) \cap N(v) \rvert \geq n-1.
\end{equation}
But we also know something about the size of the union, $\lvert N(u) \cup N(v) \rvert$. There are only $n$ vertices in all, and of those, neither $u$ nor $v$ can be in either of the two neighborhoods. Each of them certainly isn't adjacent to itself. And we are explicitly considering the case where $u$ and $v$ are not adjacent to each other. Therefore, only $n-2$ other vertices remain as possible neighbors:
\begin{equation}\label{available-vertices}
\lvert N(u) \cup N(v) \rvert \leq n-2.
\end{equation}
We can reverse the direction of Inequality~\ref{available-vertices} from $\leq$ to $\geq$ if we multiply both sides by $-1$:
\begin{equation}\label{negated-available-vertices}
-\lvert N(u) \cup N(v) \rvert \geq 2-n.
\end{equation}
If we now add Inequality~\ref{negated-available-vertices} to Inequality~\ref{union-intersection}, we get
\[\lvert N(u) \cap N(v) \rvert \geq 1.\]
In other words, the nonadjacent vertices $u$ and $v$ have at least one neighbor in common. This shows that the distance from $u$ to $v$ is $2$, completing the proof that the graph $G$ is connected with diameter at most $2$.
\end{proof}
\end{document}