\documentclass[11pt]{scrartcl}
\usepackage[headheight=1pt, includeheadfoot, headsep=1cm, top=1.5cm, bottom=1.3cm, left=2cm, right=2cm]{geometry}
\usepackage{mathtools}
\usepackage{amsmath,amsthm, amscd, amssymb, amsfonts}
\usepackage[english]{babel}
\usepackage{fancyhdr}
\usepackage{enumitem}
\setlist{itemsep=0.5em}
\usepackage{xcolor}
\definecolor{forestgreen}{rgb}{0.13, 0.55, 0.13}
\usepackage[colorlinks = true,
linkcolor = forestgreen,
urlcolor  = forestgreen,
citecolor = forestgreen,
anchorcolor = forestgreen]{hyperref}
\usepackage{multicol}
\usepackage{multienum}
\usepackage{euler}
\usepackage[OT1]{eulervm}
\renewcommand{\rmdefault}{pplx}
\usepackage{tikz}
\usepackage{mathabx}
\usepackage{lastpage}






%% header, footer definitions
\def\course{MATH 314}
\def\courselink{https://www.gsanmarco.com/graph-theory}
\def\assignment{HW \#10}
\def\assignlink{hw10.tex}
\def\due{Due on April 11}




\pagestyle{fancy}
\fancyhead[L]{\course}
\fancyhead[C]{\assignment} 
\fancyhead[R]{\due} 
%\renewcommand{\footrulewidth}{0.4pt}
%\fancyfoot{}
%\fancyfoot[R]{\fontsize{8}{10} \selectfont  Page \thepage~of \pageref{LastPage}}
%\fancyfoot[L]{\fontsize{10}{12} \selectfont  Source file available at \href{\courselink}{\textbf{\courselink}}}

%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}

% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{Solution}{Solution}
% custom
\newenvironment{solution}{\noindent\textbf{Solution.}}{\qed}


\DeclareMathOperator{\diam}{diam}
\newcommand*{\abs}[1]{\lvert #1\rvert}



\begin{document}
\noindent  Unless explicitly requested by a problem, do not include sketches as part of your proof. You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
\vskip10pt

\begin{problem}[1pt]
	Let $G$ be a bipartite graph with parts $U$, $W$, and  fix an integer $k\geq 1$. Show that if $\deg u\geq k$ for all $u\in U$  and $\deg w\leq k$ for all $w \in W$, then $G$ has a matching which saturates $U$.
\end{problem}
\begin{problem}[2pts]
	Let $G$ be a graph on $n\geq 2$ vertices with $\delta(G)\geq n/2$.
	Show that:
	\begin{enumerate}[label=(\alph*), leftmargin=*]
		\item If $n$ is even, then $G$ has a perfect matching.
		\item If $n$ is odd, then $G-v$ has a perfect matching for every $v\in V(G)$.
	\end{enumerate}

Hint: Hamiltonian cycles.
\end{problem}


\begin{problem}[2pts]
	Let $G$ be a $k$-regular bipartite graph.
	Prove that we can partition the edges of $G$ into $k$ perfect matchings.
	That is, show that we can can partition $E(G)=M_1\sqcup\dots\sqcup M_k$ where each $M_i$ is a perfect matching in $G$.
\end{problem}



\begin{problem}[2pts]
	Let $G$ be a bipartite graph with parts $U$, $W$ wherein no vertex of $U$ is isolated.
	Show that if all vertices in $U$ have distinct degrees, then $G$ contains a matching which saturates $U$.
\end{problem}


\begin{problem}[1+2pts]
Let $G$ be an $n$-vertex graph. Recall that the \textbf{degeneracy} of a graph $G$ is 
\[d(G)=\max\{\delta(H) \colon H \text{ is a subgraph of } G\}\]
	\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item Show that there is an ordering $V(G)=\{v_1, \dots, v_n\}$ such that $\vert N(v_i) \cap \{v_1, \dots, v_{i-1}\} \vert \leq d(G)$ for all $i \in \{1,\dots, n\}$. 
	
	Hint: induct by deleting an appropriate vertex.

	\item Use the ordering on part (a) to give an alternative proof of Theorem 10.9, i.e. $\chi(G)\leq 1 + d(G)$.
	\end{enumerate}
\end{problem}

\begin{problem}[1 bonus pt] 
Let $G$ be an $n$-vertex graph.	Show that $d(G)$ is the smallest integer $d$ such that there is an ordering $V(G)=\{v_1, \dots, v_n\}$ so that $\vert N(v_i) \cap \{v_1, \dots, v_{i-1}\} \vert \leq d$ for all $i \in \{1,\dots, n\}$. 

This problem will be graded all-or-nothing. 
\end{problem}
\end{document}