\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{\bz}{{\mathbf Z}}

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

\begin{document}

$\;$\hfill Due: 2011/10/19 before class

\begin{center}
{\LARGE\bf Homework 4}
\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$, find $n+1$ distinct subsets of $[n]$, $A_i$ ($1 \leq i \leq n+1$) such that
for each $x \in [n]$, there are $1 \leq i < j \leq n+1$ where $A_i - x = A_j - x$.
\end{hw}

\begin{hw}
Prove that, in a connected graph $G$, any 2 longest paths share a common vertex.
(Note: write your proof as convincing as possible.)
\end{hw}

\begin{hw}
Let $T$ be a tree, $T_i$ ($1 \leq i \leq k$) be subtrees of $T$.
Prove that, if any two of the $T_i$'s share a common vertex, then all the
$T_i$'s share a common vertex.
\end{hw}

\begin{hw}
For any positive integer $n$, define a graph $G = (V, E)$, where $V$ consists of points in the plane
$(i, 0)$ for $i = 0, 1, 2, ..., n+1$, $(i, 1)$ and $(i, -1)$ for $i = 1, 2, ..., n$. Two vertices are adjacent
if their distance in the plane is 1.
Find the size of $Aut(G)$.
\end{hw}

\begin{hw}
For each $n > 5$, find a graph $G$ of order $n$ for which $|Aut(G)| = 1$.
\end{hw}

\begin{hw}
Let $G$ be a graph on $n$ vertices ($n > 3$) with no vertex of degree $n-1$. Suppose that for any two vertices of
$G$, there is a unique vertex adjacent to both of them.

(a) If $u$ and $v$ are not adjacent, prove that they have the same degree. (Hint: Construct a bijection between the
two sets of neighbors.)

(b) Show that $G$ is $k$-regular for some $k$.

(c) Express $n$ in terms of $k$.

\end{hw}


\end{document}
