\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}
\renewcommand{\emptyset}{\varnothing}

\begin{document}
\headers{Math573}{Homework 5}{Due Thurs., Nov. 14, 2024}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\B}{\mathcal{B}}
\newcommand{\comp}[1]{\overline{#1}}
\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  All written work must be your own, using only permitted sources.  See the ``General Guidelines and Advice'' on the homework page for more details.

\begin{enumerate}

\item For $n\ge 4$, determine the maximum number of edges in an $n$-vertex graph $G$ in which every pair of cycles shares a common edge.

\item {} For $k>0$, let $G$ be a $k$-regular graph of even order that remains connected whenever $k-2$ edges are deleted.  Prove that $G$ has a $1$-factor.

\item {} Let $G$ be a graph, and let $H$ be the block-point forest of $G$. Recall: $H$ is the $(\B,S)$-bigraph, where $\B$ is the set of blocks, $S$ is the set of cut vertices, where a block $B$ is adjacent to a cut-vertex $u$ if and only if $u\in V(B)$.  Prove that $H$ is a forest in which every leaf belongs to $\B$.

\item {} Let $v$ be a vertex of a $2$-connected graph $G$.  Prove that $v$ has distinct neighbors $u_1$ and $u_2$ such that $G-v-u_1$ and $G-v-u_2$ are both connected.  Hint: consider the block-point forest of $G-v$.

\item {} Let $x$ and $y$ be vertices in a $3$-connected graph $G$.  Show that there is an induced $xy$-path $P$ such that $G-V(P)$ is connected.

\item {} Let $G$ be a $2k$-edge-connected graph with at most two vertices of odd degree.  Prove that $G$ has a $k$-edge-connected orientation.  (Recall that a digraph $D$ is $k$-edge-connected if $|[S,\comp{S}]| \ge k$ when $S$ is a nonempty proper subset of $V(D)$.  Here, the directed cut $[S,\comp{S}]$ is the set of all edges from vertices in $S$ to vertices outside $S$.)

\end{enumerate}
\end{document}
