\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{Maximum Cut Vertices}
\author{MCS-236}
\date{Fall 2011}
\begin{document}
\maketitle
The path $P_n$ has $n-2$ cut vertices. We can show that this is the most cut vertices for any graph of order $n$.
\begin{lemma}\label{spanning-tree-lemma}
If $T$ is a spanning tree of a nontrivial connected graph $G$, then $T$ has at least as many cut vertices as $G$ does.
\end{lemma}
\begin{proof}
Any cut vertex of $G$ is a cut vertex of $T$. because for any three vertices $u$, $v$, and $w$, if all paths from $u$ to $w$ in $G$ pass through $v$, then the same must be true in $T$.
\end{proof}
\begin{theorem}
If $G$ is a nontrivial connected graph of order $n$, then $G$ has at most $n-2$ cut vertices.
\end{theorem}
\begin{proof}
Any tree of order $n$ has at least two vertices that are not cut vertices, namely the leaves. Therefore, any spanning tree $T$ of $G$ has at most $n-2$ cut vertices. By Lemma~\ref{spanning-tree-lemma}, $G$ has no more cut vertices than $T$ does, so $G$ too has at most $n-2$ cut vertices.
\end{proof}
\end{document}
\end{document}