\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 \#8}
\def\due{Mar 29}
\def\doclink{\url{https://mathematicaster.org/teaching/graphs2022/hw/hw8.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}



\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

We say that a graph is \emph{even-regular} if every vertex has even degree, and we say that a graph is \emph{odd-regular} if every vertex has odd degree.

\begin{problem}[2pts]
    In the second week of class (01-27), we used the handshaking lemma to prove the following fact:
    If $G$ is a connected even-regular graph, then $G$ has no bridges.

    Give an alternative proof of this fact using what we now know about Eulerian circuits.
\end{problem}


\begin{problem}[2 + 2 pts]
    A digraph $D$ is said to be \emph{oriented} if $(u,v)\in E(D)\implies(v,u)\notin E(D)$, i.e.\ $D$ has no directed cycles of length $1$ or $2$.

    For a digraph $D$ with no loops, the \emph{underlying simple graph} of $D$ is the (simple) graph $G$ with $V(G)=V(D)$ and $uv\in E(G)$ if and only if $(u,v)\in E(D)$ or $(v,u)\in E(D)$.
    In other words, the underlying simple graph is formed by simply forgetting about the directions of the edges.

    For a (simple) graph $G$, an \emph{orientation} of $G$ is an oriented digraph whose underlying simple graph is $G$.
    In other words, an orientation of $G$ is formed by assigning a direction to each edge of $G$.
    Note that a graph generally has many orientations.
    \begin{enumerate}
        \item Prove that if $G$ is a (simple) even-regular graph, then $G$ has an orientation wherein $\deg^+ v=\deg^- v$ for all vertices $v$.
        \item Prove that if $G$ is any (simple) graph, then $G$ has an orientation wherein $\abs{\deg^+ v-\deg^- v}\leq 1$ for all vertices $v$.

            You are free use part 1 as a black-box even if you haven't proved it.
    \end{enumerate}
\end{problem}


\begin{problem}[2 + 2 pts]
    For graphs $G,H$, the \emph{Cartesian product} of $G$ and $H$ is the graph $G\mathbin\square H$ which has vertex set $V(G)\times V(H)$ and $\{(u_1,v_1),(u_2,v_2)\}\in E(G\mathbin\square H)$ if and only if either $u_1=u_2$ and $v_1v_2\in E(H)$ or $u_1u_2\in E(G)$ and $v_1=v_2$.\footnote{N.b.\ We like the notation $\square$ here since $K_2\mathbin\square K_2\cong C_4$, which looks like a $\square$. Note that your book uses $\times$ in place of $\square$; this is okay, but not desirable since generally $\times$ denotes a different graph product known as the categorical product, in which $K_2\times K_2\cong K_2\sqcup K_2$, which can be made to look like an $\times$.}

    Suppose that $G$ and $H$ are any graphs.
    \begin{enumerate}
        \item Prove that $G\mathbin\square H$ is connected if and only if both $G$ and $H$ are connected.
        \item Prove that $G\mathbin\square H$ is Eulerian if and only if both $G$ and $H$ are connected and also:
            \begin{enumerate}
                \item Both $G$ and $H$ are even-regular, or
                \item Both $G$ and $H$ are odd-regular.
            \end{enumerate}
            You are free to use part 1 as a black-box even if you haven't proved it.
    \end{enumerate}
\end{problem}



\end{document}
