\documentclass[11pt]{article}
%% The following commands all in one way or another set us up to be able to draw graphs.
%%
%% The calc package is used for calculating angles to evenly space vertices in circular arrangements.
\usepackage{calc}
%%
%% The tikz package is used for doing the actual drawing.
\usepackage{tikz}
%%
%% The next line says how the "vertex" style of nodes should look: drawn as small circles.
\tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=6pt]
%%
%% Next, we make a \vertex command as a shorthand in place of \node[vertex} to get that style.
\newcommand{\vertex}{\node[vertex]}
%%
%% Finally, we declare a "counter", which is what LaTeX calls an integer variable, for use in
%% the calculations of angles for evenly spacing vertices in circular arrangements.
\newcounter{Angle}
% These packages from the American Mathematical Society often come in handy:
\usepackage{amssymb, amsmath}
% I've defined a bunch of theorem-like environments here; you'll probably only ever
% use a few of them.
\newtheorem{prop}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{corollary}{Corollary}
\newtheorem{terminology}{Terminology}
\newtheorem{notation}{Notation}
\newtheorem{exercise}{Exercise}
\newtheorem{note}{Note}
\newtheorem{comment}{Comment}
\newtheorem{claim}{Claim}
% The next mess defines an environment for proofs.
\newenvironment{proofhelper}[1]%
{\begin{trivlist}\item\textbf{Proof.}#1\quad\ignorespaces}%
{\hfill\rule{1ex}{1ex}\end{trivlist}}
\newenvironment{proof}%
{\begin{proofhelper}{}}%
{\end{proofhelper}}
% The following is a variant for when the method of proof is indicated.
\newenvironment{proofmethod}[1]%
{\begin{proofhelper}{ [#1]}}%
{\end{proofhelper}}
% Below I define some shortcuts for some common symbols.
\newcommand{\R}{\mathbf{R}} % boldface R for the real numbers
\newcommand{\Z}{\mathbf{Z}} % boldface Z for the integers
\newcommand{\Q}{\mathbf{Q}} % boldface Q for the rational numbers
\newcommand{\rad}{\mathop{\mathrm{rad}}}
\newcommand{\diam}{\mathop{\mathrm{diam}}}
\title{Some Proofs about Distances and Centers}
\author{MCS-236}
\date{Fall 2011}
\begin{document}
\maketitle
\begin{theorem}
If $G$ is a graph with radius $\rad G$ and diameter $\diam G$, then $\rad G \le \diam G \le 2 \rad G$.
\end{theorem}
\begin{proof}
Because the radius is the minimum eccentricity of any vertex and the diameter is the maximum, the radius cannot be larger than the diameter.
Let $u$ and $v$ be vertices of $G$ such that $d(u,v) = \diam G$. Let $w$ be a central vertex so that $e(w) = \rad G$. This means that no vertex is at a distance greater than $\rad G$ from $w$. In particular $d(u,w)$ and $d(v,w)$ are both less than or equal to $\rad G$. Therefore, $d(u,w) + d(v,w) \le 2 \rad G$. By the triangle inequaltiy, $d(u,v) \le d(u,w) + d(v,w)$. This establishes that $\rad G \le \diam G \le 2 \rad G$.
\end{proof}
\begin{theorem}
For any graph $G$, there is some graph $H$ that has $G$ as its center.
\end{theorem}
\begin{proof}
We can construct $H$ by adding four vertices to $G$: $i_1$, $i_2$, $o_1$, and $o_2$. The new edges are $o_1i_1$, $o_2i_2$, and for all $v$ in $V(G)$, $vi_1$ and $vi_2$. The eccentricity within $H$ of all vertices in $V(G)$ is 2, whereas the eccentricity of the added vertices is 3 for the $i$ vertices and 4 for the $o$ vertices.
\end{proof}
\begin{theorem}
For a graph $G$, there exists a graph $H$ that has $G$ as its periphery if and only if all vertices in $G$ have eccentricity 1 or no vertices in $G$ have eccentricity 1.
\end{theorem}
\begin{proof}
If all vertices in $G$ have eccentricity 1, then $G$ can itself serve as $H$. On the other hand, if no vertices in $G$ have eccentricity 1, then $H$ can be formed by adding one new vertex, $s$, and for each vertex $v$ in $V(G)$, the edge $sv$.
To show the converse, suppose that $G$ has a vertex $u$ that has eccentricity 1, other vertices $v$ and $w$ that have eccentricities greater than 1, and yet $G$ is the periphery of some graph $H$. We show this leads to a contradiction.
We know that the diameter of $G$ is greater than $1$. Because $G$ is an induced subgraph of $H$, the diameter of $H$ is also greater than $1$.
Since $G$ is the periphery of $H$, any vertex in $V(G)$, such as $u$, must have $e_H(u) = \diam H > 1$.
%Since $G$ is the periphery of $H$, then all vertices of $G$ must have equal eccentricity that is greater than $1$.
Since $e_G(u)=1$, there must be some vertex $s$ in $V(H)-V(G)$ that $u$ is farthest from. However, $s$ also has eccentricity equal to $e_H(u)$ yet is not included in the periphery, producing a contradiction.
\end{proof}
\end{document}