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

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

\begin{document}
\headers{Math573}{Homework 6}{Due Tues, Nov. 28, 2017}

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

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

\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}


\newcommand{\comp}[1]{\overline{#1}}

\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$.)

\item {} Minimally $k$-edge-connected graphs.
\begin{enumerate}
    \item For $S\subseteq V(G)$, let $d(S) = |[S,\comp{S}]|$.  Let $X$ and $Y$ be nonempty proper vertex subsets of $G$.  Prove that $d(X\cap Y) + d(X\cup Y) \le d(X) + d(Y)$.  Hint: the sets $X\cap Y$, $X-Y$, $Y-X$, and $\comp{X}\cap \comp{Y}$ partition $V(G)$.  Draw a picture in which $V(G)$ is organized by this partition and consider contributions from various types of edges.
    \item A $k$-edge-connected graph $G$ is \emph{minimally $k$-edge-connected} if, for each edge $e$ in $G$, the graph $G-e$ is not $k$-edge-connected.  Prove that $\delta(G) = k$ when $G$ is minimally $k$-edge-connected.  Hint: Consider a minimal set $S$ such that $|[S,\comp{S}]| = k$.  If $|S| \ne 1$, then use $G-e$ for some $e\in E(G[S])$ to obtain another set $T$ with $|[T,\comp{T}]| = k$ such that $S,T$ contradict part (a).
\end{enumerate}

\item {} Use network flows to prove Menger's Theorem for edge-disjoint paths in graphs: $\kappa'(x,y) = \lambda'(x,y)$.  (Recall that $\kappa'(x,y)$ is the minimum size of a set of edges $S$ such that $G-S$ has no $xy$-path, and $\lambda'(x,y)$ is the maximum size of a set of edge-disjoint $xy$-paths.)

\item {} Let $G$ be a graph whose odd cycles are pairwise intersecting, meaning that every two odd cycles in $G$ have a common vertex.  Prove that $\chi(G)\le 5$.

\item {} Let $G$ be a graph with no induced copy of $P_4$, let $k=\omega(G)$, and let $\sigma$ be an ordering of $V(G)$.  Prove that with respect to $\sigma$, the greedy algorithm produces a proper $k$-coloring of $G$.  Hint: show that if a vertex $u$ receives color $j$, then $u$ completes a $j$-clique with vertices that precede $u$ in $\sigma$.


\end{enumerate}
\end{document}
