\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}

\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}

\usepackage{enumitem}
\setlist{itemsep=0.5em}

%% header definitions
\def\course{MATH 314}
\def\assign{HW \#9}
\def\due{Apr 5}
\def\doclink{\url{https://mathematicaster.org/teaching/graphs2022/hw/hw9.tex}}

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

% custom
\newenvironment{solution}{\paragraph{Solution.}}{\qed}

%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}}       % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}}        % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert}     % absolute values, cardinality
\newcommand*{\eps}{\varepsilon}            % prettier epsilon
\newcommand*{\R}{\mathbb{R}}               % real numbers
\newcommand*{\C}{\mathbb{C}}               % complex numbers
\newcommand*{\Q}{\mathbb{Q}}               % rational numbers
\newcommand*{\Z}{\mathbb{Z}}               % integers
\newcommand*{\N}{\mathbb{N}}               % natural numbers
\newcommand*{\F}{\mathbb{F}}               % field
\newcommand*{\family}{\mathcal{F}}         % family
\newcommand*{\GL}{\mathbf{GL}}             % general linear group
\newcommand*{\what}[1]{\widehat{#1}}       % wider hat
\newcommand*{\wbar}[1]{\overline{#1}}      % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}}       % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}}         % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}}         % mathbb

% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}}       % probability
\DeclareMathOperator*{\E}{\mathbb{E}}          % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}}      % variance
\DeclareMathOperator*{\Span}{span}             % span
\DeclareMathOperator{\tr}{tr}                  % trace
\DeclareMathOperator{\rank}{rank}              % rank
\DeclareMathOperator{\supp}{supp}              % support
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\comp}{comp}



\begin{document}
\pagestyle{empty}

\noindent
\begin{minipage}{.33\textwidth}
	\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
	\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt

\noindent {\footnotesize This document is from \doclink}
\vskip10pt

\noindent {\small 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.
}

\vskip20pt

\begin{problem}[1 + 2 pts]
    Fix any integer $n\geq 3$.
    \begin{enumerate}
        \item Construct an $n$-vertex graph $G$ with ${n-1\choose 2}+1$ many edges such that $G$ is \emph{not} Hamiltonian.

            (Note: You must construct such a graph for \emph{every} $n\geq 3$.)
        \item Prove that if $G$ is an $n$-vertex graph with at least ${n-1\choose 2}+2$ many edges, then $G$ is Hamiltonian.
    \end{enumerate}
\end{problem}


\begin{problem}[0.5 + 0.5 pts]
    Recall that $K_{n_1,n_2,n_3}$ is the complete tripartite graph with parts of sizes $n_1,n_2,n_3$.

    Fix any positive integer $n$.
    \begin{enumerate}
        \item Prove that $K_{n,2n,3n}$ is Hamiltonian.
        \item Prove that $K_{n,2n,3n+1}$ is not Hamiltonian.
    \end{enumerate}
\end{problem}


\begin{problem}[2pts]
    Let $G$ be a graph on $n\geq 4$ vertices with the property that $N(u)\cup N(v)\supseteq V(G)\setminus\{u,v\}$ for every $u\neq v\in V(G)$.
    Prove that $G$ is Hamiltonian.

    (Hint: $\abs{A\cup B}=\abs A+\abs B-\abs{A\cap B}$ for finite sets $A,B$.)

    (Hint: The problem and first hint suggest attempting a proof similar to our proof of Bondy--Chv\'atal, i.e.\ extending a Hamiltonian path to a Hamiltonian cycle. While such a proof is possible, it's more difficult than a more direct proof using only Ore's condition. This is just my opinion and maybe you disagree; I just don't want to lead you down the wrong path.)
\end{problem}




\begin{problem}[2pts]
    Let $G$ be a graph on $n$ vertices.
    In class, we showed that $\alpha'(G)+\beta'(G)=n$ provided $G$ has no isolated vertices; this exercise exists to establish the natural (and easier to prove) vertex-version of this fact.

    Recall that the independence number of $G$, denoted by $\alpha(G)$, is the size of a largest independent set of $G$.
    Recall also that the vertex-cover number of $G$, denoted by $\beta(G)$, is the size of a smallest vertex-cover of $G$.

    Prove that $\alpha(G)+\beta(G)=n$ for any $n$-vertex graph $G$.

    (Note: You don't need to know anything about matchings to prove this.)
\end{problem}


\begin{problem}[2 pts]
    We have an $m\times n$ matrix $M\in\{0,1\}^{m\times n}$.
    We refer to the columns and rows of this matrix as \emph{lines} (so a line is either one of the $m$ rows or one of the $n$ columns of $M$).
    Prove that the minimum number of lines needed to contain all $1$'s of $M$ is precisely the maximum number of $1$'s in $M$ that one can select so that no two of these selected $1$'s live in any common line.
\end{problem}





\end{document}
