\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}