\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 301 Homework}
\author{Mary Radcliffe}
\date{Due 3 November 2017}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item \begin{enumerate}
\item Let $G$ be a graph of order $n\geq 4$, and having $m\geq \frac{n+n\sqrt{4n-3}}{4}+1$. Prove that $G$ contains a 4-cycle.
\item  Let $G$ be a graph of order $n\geq 4$ and having $m\geq \frac{n}{2}\sqrt{n-1}+1$ edges. Prove that $G$ contains either a 3-cycle or a 4-cycle.
\end{enumerate}

\item Let $G=(V, E)$ be a graph with average degree $D$. Show that there exists a subgraph $H$ in $G$ with $\delta(H)\geq \frac{D}{2}$, that is, the minimum degree in $H$ is at least $\frac{D}{2}$.

\item Let $T$ be a tree on $k$ vertices. Prove that $\frac{n(k-2)}{2}\leq ex(n, T)\leq nk$ for any $n\in \N$ having $n$ divisible by $k-1$. Prove that there exists at least some trees for which the lower bound is in fact equal to $ex(n, T)$.

NOTE: We do not know the extremal numbers for trees, in general. It has been conjectured (Erd\H{o}s-S\'{o}s Conjecture) that the lower bound above is in fact equal to the extremal number for all trees, but the conjecture has been open since 1963. 

\item For $0<s\leq t\leq n$, define $z(n, s,t)$ to be the maximum number of edges in a bipartite graph $G$, with partite sets $V_1, V_2$ such that $|V_1|=|V_2|=n$ and $K_{s, t}\not\subseteq G$. Prove that $2ex(n, K_{s, t})\leq z(n, s, t)\leq ex(2n, K_{s, t})$.
\end{enumerate}
\end{document}