% This template was created by Stephen on 27th March 2000


% Set the document class
\documentclass[12pt,a4paper]{article}

% Resize the page, to save the forests.
\setlength{\topmargin}{-1cm} \setlength{\textheight}{24cm}
\setlength{\textwidth}{15cm} \setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}

% Just in case we want to do Black Board Bold letters.
%\input{amssymb.sty}
\usepackage{amssymb}

% So we can do multicolumns
\usepackage{multicol}
\setlength\columnseprule{0pt}   % no vertical lines inbetween columns
\setlength\multicolsep{0.5ex}     % space preceding a multicolumn

% A command to generate the header text
\newcommand{\myheader}
{\footnotesize December 2005}

% Change the headers and footers
\pagestyle{myheadings} \markboth{\myheader}{\myheader}

% New Commands to make numbered lists easier
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}

% New Commands to make in-text displayed math easier
\newcommand{\bdm}{$ \displaystyle}
\newcommand{\edm}{$}

% New Commands to do handle the black board bold sets:
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}

% New command for conjugates, arguments, etc.
\def\conj#1{\overline{#1}}
\def\arg{\,\mbox{arg}\,}
\def\Arg{\,\mbox{Arg}\,}
\def\cis{\,\mbox{cis}\,}
\def\Cis#1{\cos {#1} + i \sin {#1}}
\def\Re{\, \mbox{Re}\,}
\def\Im{\, \mbox{Im}\,}
\def\cosec{\,\mbox{cosec}\,}
\def\deg{\,\mbox{deg}\,}

% New command for does not divide
\def\notdivide{\!\not|\,}

% for f:X -> Y; the default spacing isn't great
\newcommand{\map}[2]{\,{:}\,#1\!\longrightarrow\!#2}

% New command for the heading
\newcommand{\WorksheetHeading}[1]{{\par\noindent \bf \Large #1}}

% New command to fix spelling
\newenvironment{centre}{\begin{center}}{\end{center}}

% New command for itemised titles
\def\it#1{\item{\bf #1.}}

%--------------------------------------------------------
% Let the document begin!
\begin{document}

\begin{centre}
  \bf \Large
 Graph Theory (J)
\end{centre}

\subsection*{Problems}

\begin{enumerate}

\item Prove that in any connected graph, any two longest paths
intersect.

\item Prove that a graph with no cycles and at least one edge has
at least two vertices of degree 1.

\item Prove that amongst six people, we can find a group of three
who are either all friends or all not friends.

\item (IMO 1964) Each pair from 17 people exchange letters on one
of three topics. Prove that there are at least 3 people who write
to each other on the same topic.

\item Prove that a graph is traversible if and only if it has
either 0 or 2 vertices of odd degree.

\item $n\geq2$ people meet in a room. Everyone shakes hands with
everyone else. Prove that during the greeting ceremony there are
always two people who have shaken the same number of hands.

\item Prove that a graph is bipartite if and only if it contains
no cycles of odd lengths.

\item A polyhedron with an even number of edges is given. Prove
that an arrow can be placed on each edge so that each vertex is
pointed to by an even number of arrows.

\item Suppose a graph has $n$ vertices and $2m$ edges. Show that
we can divide the vertices into two groups such that there are at
least $m+1$ edges \lq broken'.

\item Prove that a graph with $n$ vertices and more than $n^2/4$
edges must contain a triangle.

\item (Klamkin) Ten airlines serve a total of 1983 cities. There
is a direct service (no stopover) between any two cities, and if
an airline offers a direct flight from $A$ to $B$, it also offers
a direct flight from $B$ to $A$. Prove that at least one of the
airlines provides a round trip with an odd number of landings.

\item Find the smallest $n>4$ for which there exists a set of
people such that
\begin{enumerate}
\item any two acquaintances have no common acquaintance. \item any
two unacquainted people have exactly two common acquaintances.
\end{enumerate}
NB: if $A$ is acquainted to $B$, then $B$ is acquainted to $A$.

\item Each of the members of parliament in the land of Achronia
has exactly one friend and one enemy among the other members of
parliament. Prove that the parliament can be divided into two
chambers so that inside each of the chambers there are no friends
and no enemies.

\item There is a finite number of towns in a country. They are
connected by one-direction roads. It is known that, for any two
towns, one of them can be reached from the other one. Prove that
there is a town such that all the remaining towns can be reached
from it.

\item Every road in Sikina is one-way. Every pair of cities is
connected by one direct road. Show that there exists a city which
can be reached from every other city directly or via at most one
other city.

\item There are $N$ towns connected by $2N-1$ one-way roads.
Suppose that it is possible to reach any town starting at any
other one. Prove that there exists a road that can be closed while
preserving the above condition.

\item (1987 AMO) In the country Patera, there are 20 cities and
two airline companies, Green Planes and Red Planes, to provide
communication between cities. The flights are arranged as follows.
\begin{enumerate}
\item Given any two cities in Patera, one and only one of the
companies provides direct flights (in both directions and without
stops) between the two cities. \item There are two cities, $A$ and
$B$ in Patera such that a journey cannot be made (with possible
stops) using only Red Planes.
\end{enumerate}
Show that, given any two cities in Patera, a passenger can travel
from one to the other using only Green Planes, making at most one
stop in some third city.

\item (1988 AMO) A city has a system of bus routes laid out such
that \begin{enumerate} \item There are exactly 11 bus stops on
each route, \item It is possible to travel between any two bus
stops without changing routes, \item Any two bus routes have
exactly one bus stop in common.
\end{enumerate}
What is the number of bus routes in the city?

\item If a graph on $n$ vertices has $e$ edges, show that it has
at least $\frac{e}{3n}(4e-n^2)$ triangles.

\end{enumerate}


\end{document}
