\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{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


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

\begin{document}
\title{Math 301: Homework 7}
\author{Mary Radcliffe}
\date{due 11 Nov 2016}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Prove that if $G$ is a $k$-regular bipartite graph, then the edges of $G$ can be partitioned into disjoint sets $M_1, M_2,\dots, M_k$, where each $M_k$ is a perfect matching in $G$.

\item Let $T$ be a tree.
\begin{enumerate}
\item Prove that $T$ has at most one perfect matching.
\item Prove that $T$ has exactly one perfect matching if and only if for every vertex $v\in V(T)$, the number of odd-sized components of $T\ba\{v\}$ is 1.
\end{enumerate}

\item A {\it bridge} in a graph $G$ is an edge $e$ such that $G\ba\{e\}$ has more components than $G$. A graph is {\it bridgeless} if it has no bridges.

Let $G$ be a bridgeless, 3-regular graph. Prove that $G$ contains a perfect matching.

\end{enumerate}

\end{document}