\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. 9, 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}

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

\newcommand{\matTT}[9]%
{%
    \left( %
    \begin{array}{ccc}
        #1 & #2 & #3 \\
        #4 & #5 & #6 \\
        #7 & #8 & #9
    \end{array}
    \right) %
}

\item {} A \emph{doubly stochastic matrix} $Q$ is a nonnegative real matrix in which every row and every column sums to 1.  Prove that a doubly stochastic matrix $Q$ can be expressed as $Q=c_1P_1 + \cdots + c_m P_m$ where $c_1, \ldots, c_m$ are nonnegative real numbers summing to $1$ and $P_1, \ldots, P_m$ are permutation matrices.  For example,
\[ \matTT{1/2}{1/3}{1/6}{0}{1/6}{5/6}{1/2}{1/2}{0} = 
\frac{1}{2} \matTT{1}{0}{0}{0}{0}{1}{0}{1}{0} 
+ \frac{1}{6} \matTT{0}{0}{1}{0}{1}{0}{1}{0}{0} 
+ \frac{1}{3} \matTT{0}{1}{0}{0}{0}{1}{1}{0}{0} \]
Hint: Use induction on the number of nonzero entries in $Q$.    

\item {} Determine the maximum number of edges in a bipartite graph that contains no matching with $k$ edges and no star with $l$ edges.  (Your answer should provide a construction and prove it is best possible.)

\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 {} Connectivity and perfect matchings.  
\begin{enumerate}
    \item Let $G$ be an $r$-connected graph of even order having no $K_{1,r+1}$ as an induced subgraph.  Prove that $G$ has a $1$-factor.
    \item For each $r$, construct an $r$-connected graph of even order that does not contain an induced copy of $K_{1,r+3}$ and has no $1$-factor.
\end{enumerate}
(Comment: this leaves unresolved whether every $r$-connected graph of even order without an induced copy of $K_{1,r+2}$ has a $1$-factor.  Note: when the number of vertices is even, the inclusion bigraph between $(r-1)$-sets and $r$-sets in $[2r]$ is a candidate for a sharpness example.  This graph has no induced $K_{r+2}$ and no perfect matching.  Probably it is $r$-connected.  Can you prove it?)

\item {} Let $v$ be a vertex of a $2$-connected graph $G$.  Prove that $v$ has a neighbor $u$ such that $G-u-v$ is connected.  Find a $2$-edge-connected graph $G$ that has a vertex $v$ such that for each neighbor $u$ of $v$, the graph $G-u-v$ is disconnected.


\end{enumerate}
\end{document}
