\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Do not need to hand in.

\begin{center}
{\LARGE\bf Homework 6}
\end{center}

\begin{hw}
Prove that, if $G$ is a $k$-regular ($k \geq 1$) bipartite graph with bipartition $A$ and $B$, then $|A| = |B|$.
\end{hw}

\begin{hw}
For each $n > 5$, find a graph $G$ of order $n$ for which $|Aut(G)| = 1$.
(In addition, you may check that any graph $G$ on $[2]$, $[3]$, or $[4]$
has $|Aut(G)| > 1$.)
\end{hw}

\begin{hw} A proper colouring of a graph $G$ with $c$ colours is a mapping
$f: V(G) \rightarrow [c]$ such that no adjacent vertices receive the same
colour. i.e. $f(u) \neq f(v)$ whenever $u \sim v$.

(a) Let $T$ be a tree on $[n]$ where $n > 1$. How many proper colourings
for $T$ are there with $c$ colours? Find a closed formula.
(a.1) Give a combinatorial proof to your answer. (a.2) Give
a proof using I-E. (Please do this, it is a nice exercise on
I-E, combinatorial numbers, and the trees.)

(b) How many proper colourings with $c$ colours are there for
the cycle $C_n$? Find a closed formula and prove it using I-E.
\end{hw}

\begin{hw}
Prove that, for any $f: E(K_6) \rightarrow \{Y, B\}$, there are
at least two monochromatic triangles.
\end{hw}

\begin{hw}
Given two graphs $G$ and $H$, where $V(G)$ and $V(H)$ are disjoint,
their {\em join} is defined to be the graph with a copy of $G$,
a copy of $H$ and additional edges joining all the pairs between $G$
and $H$. Formally,
\[ G \vee H = (V(G) \cup V(H), E(G) \cup E(H) \cup \{uv : u \in V(G), v \in V(H)\} ).\]

Clearly, $K_3 \vee C_5$ does not contain a copy of $K_6$. Prove that,
if its edges are coloured Y and B, there is always a monochromatic
$K_3$.
\end{hw}

\end{document}
