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

\newcommand{\kgmcomment}[1]{}
\newcommand{\ZZ}{\mathbb{Z}}
\renewcommand{\gcd}{\mathrm{gcd}}

\DeclareMathOperator{\ord}{ord}

\begin{document}
\headers{Math773}{Homework 1}{Due Thurs, Jan 26, 2016}

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

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



\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\newcommand{\RR}{\mathbb{R}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item {} A \emph{chord} of a cycle $C$ is an edge $e\in E(G) - E(C)$ that has both endpoints on $C$.  
\begin{enumerate}
	\item Show that if $\delta(G) \ge 3$, then $G$ has a cycle with a chord.
	\item Prove that for $n\ge 4$, if $G$ has at least $2n-3$ edges, then $G$ has a cycle with a chord.
\end{enumerate}

\item {} Prove that an $n$-vertex graph with $m$ edges has at least $\frac{m}{3n}(4m-n^2)$ triangles.  (Hint: adapt a proof form class.)

\item {} Recall that a \emph{decomposition} of a graph $G$ is a list of subgraphs $H_1, \ldots, H_t$ such that each edge in $G$ appears in exactly one of $\{H_1,\ldots,H_t\}$; the \emph{size} of the decomposition $H_1, \ldots, H_t$ is $t$.
\begin{enumerate}
	\item Prove that each graph $G$ has a matching of size at least $\delta(G)/2$.
	\item Use part (a) to show that each $n$-vertex graph has a decomposition into triangles and edges of size at most $n^2/4$.  (Hint: first handle edges incident to a vertex $u$ of minimum degree, and then apply induction to an appropriate subgraph of $G-u$.)
\end{enumerate}

\item {} For a vertex $v$ in an $n$-vertex graph $G$, let $f(v) = \alpha(G[N(v)])$; that is, $f(v)$ is the maximum size of an independent set in the neighbors of $v$.  Prove that $\sum_{v\in V(G)} f(v) \le \floor{n^2/2}$ and determine which graphs achieve equality.

\item {} Let $G$ be an $n$-vertex graph and let $S$ be the set of nonnegative vectors in $\RR^n$ that sum to $1$.  Given an $n$-vertex graph $G$, define $f(x)=\sum_{uv \in E(G)} x_ux_v$, and let $M=\max_{x\in S} f(x)$.
\begin{enumerate}
	\item Prove that $M=\frac{1}{2}(1-\frac{1}{r})$, where $r=\omega(G)$.  (Recall that $\omega(G)$ is the maximum size of a clique in $G$.)  (Hint: if $uv\not\in E(G)$, then show that $f(x') \ge f(x)$ for some $x'$ with $x_ux_v = 0$.) 
	\item Show that $|E(G)| \le \frac{n^2}{2}(1-\frac{1}{r})$.
	\kgmcomment{
	\item Prove that $M$ is attained by an $x\in S$ with all coordinates non-zero if and only if $G$ is a complete $r$-partite graph.  (Hint: if $G$ contains vertices $u,v,w$ with $uv, vw\not\in E(G)$ and $uw\in E(G)$, and $x\in S$ has all positive coordinates, show that $f(x')\ge f(x)$ for some $x'\in S$ whose positive coordinates induce a graph without a copy of $K_r$.)
	\item Conclude that equality holds in part (b) if and only if $G$ is the complete $r$-partite multigraph with all parts of equal size.
	}	
\end{enumerate}
Comment: it is also possible to derive the structure of extremal examples from this proof with some additional work.  Start by showing that $M$ is attained by an $x\in S$ with all positive coordinates if and only if $G$ is a complete $r$-partite graph.

\item {} Let $G$ be a connected graph such that $d(u)+d(v) \ge k$ whenever $uv\not\in E(G)$.  Prove that $G$ is Hamiltonian or has a copy of $P_{k+1}$.
 
\end{enumerate}
\end{document}
