\documentclass[12pt]{article}
\usepackage{fullpage, amsmath, amssymb, amsthm, amscd, setspace, bm, graphicx, indentfirst, multirow, tikz, enumerate}
\usepackage{adjustbox,amsfonts,array,graphicx,booktabs,tabularx,multirow,multicol,stmaryrd, tabu}
\usepackage[utf8]{inputenc}
\usetikzlibrary{arrows.meta}
\title{Math 412, Fall 2023 -- Homework 7}
\date{}
\setlength{\parskip}{0.5cm}
\setlength{\parindent}{0cm}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ba}{\overline}
\newcommand{\Hom}{\text{Hom}}
\newcommand{\End}{\text{End}}
\newcommand{\wt}[1]{\text{wt}({#1})}
\begin{document} \maketitle
\vspace{-80pt}

\textbf{Due:} Wednesday, October 25th, at 9:00AM via Gradescope

\textbf{Instructions:} Students taking the course for three credit hours (undergraduates, most graduate
students) should choose four of the following five problems to solve and turn in--if you do all five, only the first four will be graded. Graduate students
taking the course for four credits should solve all five. Problems that use the word ``describe”,
``determine”, ``show", or ``prove" require proof for all claims.

\begin{enumerate}

\item[1.] Prove that every graph $G$ with no isolated vertices has a matching of size at least $\frac{n(G)}{1+\Delta(G)}$.

\item[2.] Let $G$ be a simple graph with $\Delta(G)\leq 3$. Prove that $\kappa(G)=\kappa'(G)$.

\item[3.] Let $G$ be $k$-connected and let $U_1,U_2\subseteq V(G)$ be disjoint sets with $|U_1|=|U_2|=k$. Prove that there are $k$ pairwise disjoint paths, each of which have one endpoint in $U_1$ and the other endpoint in $U_2$.

\item[4.] Prove that the hypercube $Q_k$ is $k$-connected.

\item[5.] Draw a graph $G$ with $n$ vertices and $\kappa(G)=k$ for the following values of $n$ and $k$.

\begin{enumerate}
    \item $n=9, k=3$
    \item $n=9, k=4$
    \item $n=10, k=3$
    \item $n=10, k=4$
\end{enumerate}

\emph{[Hint: see Example 4.1.4]}

\end{enumerate}




\end{document}
