\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
\title{Some Proofs about Tournaments}
\author{MCS-236}
\date{Fall 2011}
\begin{document}
\maketitle
\begin{theorem}
If $u$ is a maximum-outdegree vertex in a tournament, then for any other vertex $v$, at least one of the following is true:
\begin{enumerate}
\item $(u,v)$ is an arc;
\item $(u,w)$ and $(w,v)$ are arcs, for some vertex $w$.
\end{enumerate}
\end{theorem}
\begin{proof}
We can distinguish two cases: either $u$ is adjacent to $v$ or $v$ is adjacent to $u$. In the first case, the conclusion is immediate: $(u,v)$ is an arc.
In the alternate where $(v,u)$ is an arc, that arc already accounts for a portion of $v$'s outdegree. In order that $v$ has no greater outdegree than $u$ does, $v$ cannot be adjacent to all of the vertices $u$ is adjacent to. So there must be some vertex that $u$ is adjacent to that $v$ is not adjacent to. Call that vertex $w$. Then there are arcs $(u,w)$ and $(w,v)$.
\end{proof}
\begin{theorem}\label{path-theorem}
If $v_1,v_2,\ldots,v_n$ is a path in a tournament and $x$ is a vertex not on the path, then at least one of the following is a path:
\begin{enumerate}
\item $x,v_1,v_2,\ldots,v_n$
\item $v_1,v_2,\ldots,v_n,x$
\item $v_1,v_2,\ldots,v_i,x,v_{i+1},\ldots,x$ for some $i$
\end{enumerate}
\end{theorem}
\begin{proof}
If $(x,v_1)$ or $(v_n,x)$ is an arc, then case 1 or 2 applies. Thus we need only consider the case where $(v_1,x)$ and $(x,v_n)$ are arcs. We can find a value of $i$ where $(v_i,x)$ and $(x,v_{i+1})$ are arcs using the following algorithm. Initialize $i$ to $1$. So long as $(v_{i+1},x)$ is an arc, increment $i$. This must terminate at worst when $i+1=n$. Then $v_1,v_2,\ldots,v_i,x,v_{i+1},\ldots,x$ is a path.
\end{proof}
\begin{corollary}
Every tournament has a Hamiltonian path.
\end{corollary}
\begin{proof}
A trivial path can be chosen arbitrarily and extended by Theorem~\ref{path-theorem} until it forms a Hamiltonian path.
\end{proof}
\begin{theorem}
A tournament is Hamiltonian if and only if it is strong.
\end{theorem}
\begin{proof}
If the tournament is Hamiltonian, it is strong because there is a path along the Hamiltonian cycle between any two vertices.
If the tournament is strong, then we can also show it is Hamiltonian. Because the tournament is strong, it contains some cycle $c_1,c_2,\ldots,c_n,c_1$. If there is some vertex $v$ not on the cycle, and arcs exist $(c_j,v)$ and $(v,c_k)$ for some $j$ and $k$, then we can find a value of $i$ such that the arcs $(c_i,v)$ and $(v, c_{i+1})$ exist using the same algorithm as in the prior proof. Thus $c_1,c_2,\ldots,c_i,v,c_{i+1},\ldots,c_n,c_1$ is a longer cycle.
On the other hand, if there are vertices not on the cycle, but none such as the vertex $v$ just described, then it must be the case that all vertices not on the cycle are in one of two sets. One set is the successors of the cycle, which is to say, vertices that have arcs from all vertices on the cycle. The other set is the predecessors of the cycle, vertices that have arcs to all vertices of the cycle. Any path from a successor to a predecessor must have an arc that leads from a successor $s$ to a predecessor $p$. Then $c_1,c_2,\ldots,c_n,s,p,c_1$ is a longer cycle.
Thus, so long as a cycle doesn't include all the vertices, it can be made longer. As such, a Hamiltonian cycle must exist.
\end{proof}
\end{document}