\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 4}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday October 22nd 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}[Infinite Semi-Eulerian Graphs, 80 points]
Define a semi-infinite trail on a graph $G$ to be a sequence of vertices $v_1,v_2,v_3,\ldots$ so that for each $i$ there is an edge in $G$ between $v_i$ and $v_{i+1}$ and so that these edges are all distinct. Call $G$ semi-Eulerian if there exists such a trail that uses every edge of $G$ exactly once. For this problem, we will consider graphs $G$ with infinitely many vertices and edges for which each vertex is incident on only finitely many edges (and thus has a well defined degree).
\begin{enumerate}[(a)]
\item Show that if $G$ has a semi-infinite Eulerian trail starting at a vertex $v$, then $\deg(v)$ is odd and all other degrees in $G$ are even, and that $G$ is connected except for isolated vertices. [20 points]
\item Unfortunately, the conditions in (a) are not sufficient. Give an example of a graph $G$ with a vertex $v$ of odd degree and all other degrees even so that $G$ does not have a semi-Eulerian trail. [20 points]
\item Show that any graph $G$ with a semi-infinite Eulerian trail must satisfy the following property: If $G'$ is any subgraph of $G$ obtained by removing finitely many edges of $G$, $G'$ contains only one connected component of infinite size. [20 points]
\item It turns out that the conditions in (a) and (c) together are sufficient. The proof relies on the following Lemma: Suppose $G$ is a graph with only one vertex $v$ of odd degree and satisfying the condition in (c). If $P$ is any finite path starting at $v$, then the edges of all of the finite connected components of $G-P$ can be partitioned into circuits. Prove this lemma. [20 points]
\end{enumerate}
\end{ques}

\begin{ques}[Toughness of Hamiltonian Graphs, 20 points]
Let $G$ be a Hamiltonian graph and let $\{v_1,v_2,\ldots,v_k\}$ be a set of $k$ vertices of $G$ for some $k\geq 1$. Let $G'$ be the subgraph of $G$ obtained by removing all of the vertices $v_i$ and all of their edges from $G$. Prove that $G'$ has at most $k$ connected components.
\end{ques}

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

\end{document} 