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

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

\begin{document}
\headers{Math573}{Homework 2}{Due Thu, Sept. 26, 2024}

%\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 {} Graphs defined algebraically.
\begin{enumerate}
    \item Let $G_n$ be the graph whose vertices are the permutations of $\{1,\ldots,n\}$ with two permutations adjacent if they differ by interchanging a pair of adjacent entries.  Note that $G_3 = C_6$.  Prove that $G_n$ is connected.
    \item Let $H_n$ be the graph whose vertices are the permutations of $\{1,\ldots,n\}$ with two permutations adjacent if they differ by interchanging a pair of entries (which may or may not be adjacent).  Note that $H_3 = K_{3,3}$ and $G_n$ is a subgraph of $H_n$.  Prove that $H_n$ is bipartite.  Hint: for each permutation $a_1 \cdots a_n$, count the pairs $(i,j)$ with $i < j$ and $a_i > a_j$; these are called \emph{inversions}.
\end{enumerate}

%\item {} [IGT 1.2.18] Let $G_k$ be the graph whose vertex set is the set of $k$-tuples with elements in $\{0,1\}$, with $x$ adjacent to $y$ if $x$ and $y$ differ in exactly two positions.  Determine the number of components of $G_k$.

\item {} Forbidden induced subgraphs.
\begin{enumerate}
    \item Let $G$ be a connected graph not having $P_4$ or $C_3$ as an induced subgraph.  Prove that $G$ is a biclique.
    \item Let $G$ be a connected graph not having $P_4$ or $C_4$ as an induced subgraph.  Prove that $G$ has a vertex adjacent to all other vertices.  (Hint: consider a vertex of maximum degree.)
\end{enumerate}

\item {} Let $P$ and $Q$ be paths of maximum length in a connected graph $G$.  Prove that $P$ and $Q$ have a common vertex.

\item An $xy$-trail $W$ is \emph{greedy} if every edge incident to $y$ is contained in $W$.  Let $G$ be an Eulerian graph, and let $x$ be a vertex in $G$.  Prove that every greedy trail starting from $x$ is an Eulerian circuit if and only if every cycle in $G$ contains $x$. 

\item {} Cut-edges and degrees.
\begin{enumerate}
        \item Prove that an even graph has no cut-edge.  For each $k\ge 1$, construct a $(2k+1)$-regular graph having a cut-edge.
        \item For $k\ge 2$, prove that a $k$-regular bipartite graph has no cut-edge.
\end{enumerate}

\item {} Counting cycles.
\begin{enumerate}
	\item Count the cycles of length $n$ in $K_n$.
	\item Count the cycles of length $2n$ in $K_{n,n}$.
	\item Count the cycles of length $5$ in the Petersen graph.
\end{enumerate}

\end{enumerate}
\end{document}
