\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}



\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}


\title{Math 154 Homework 1}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday October 1st at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.

Please cite any other students with whom you collaborated on any problems.

\begin{ques}[$2$-Regular Graphs, 25 points]
Show that any finite, $2$-regular graph $G$ is a disjoint union of cycles. In particular, show that $G$ has a number of induced subgraphs that are cycles and so that:
\begin{enumerate}
\item Each vertex is in exactly one of these induced subgraphs.
\item No edges connect these subgraphs to each other.
\end{enumerate}
\end{ques}

\begin{ques}[Properties Inherited by Subgraphs, 25 points]
For which of the following graph properties $P$ does the following hold: If $G$ is a graph satisfying $P$ and $H$ is an induced subgraph of $G$, then $H$ must also satisfy $P$. For each property, either give a proof or a counter-example.
\begin{enumerate}[(a)]
\item $G$ is a complete graph [5 points]
\item $G$ is a bipartite graph [5 points]
\item $G$ is a cycle [5 points]
\item $G$ is a simple graph [5 points]
\item $G$ is a path [5 points]
\end{enumerate}
\end{ques}

\begin{ques}[Hypergraph Handshake Lemma, 25 points]
Suppose that you have a hypergraph where each edge is incident on exactly $k$ vertices. Formulate and prove a version of the Handshake Lemma for this type of graph.
\end{ques}

\begin{ques}[$3$-Regular Graphs, 25 points]
Show that for every even integer $n\geq 4$ that there is a $3$-regular graph with exactly $n$ vertices. What happens if $n$ is odd?
\end{ques}


\begin{ques}[Extra credit, 1 point]
Approximately how much time did you spend on this homework?
\end{ques}

\end{document} 