\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2011/11/30 before class

\begin{center}
{\LARGE\bf Homework 9}
\end{center}

\begin{hw}
Let $g = 2k > 2$ be an even number. Prove that, if a graph $G$ has minimum degree $d > 2$ and girth $g$,
there it has at least $2((d-1)^k - 1) / (d-2)$ vertices. (Hint: Start from two adjacent vertices.)
\end{hw}

\begin{hw}
Find a graph with minimum degree 3, girth 6, and exactly 14 vertices. Briefly justify your answer.
(Hint: Construct a graph from the Fano configuration.)
\end{hw}

\begin{hw}
If $G$ is a graph on $n$ vertices and does not contain $C_4$, then $G$ has
at most $n(1 + \sqrt{4n-3}) /  4$ edges.
(Hint: Count the number of $(a, b, c)$ such that $a \sim b$ and $b \sim c$.)
\end{hw}

\end{document}
