Do three (3) problems from each section. If you work on more than the required number of problems, make sure that you clearly mark which problems you want to have counted. Standard results from the courses may be used without proof provided they are clearly marked. If you have doubts about the wording of a problem or about what results may be assumed without proof, please ask for clarification. In no case should you interpret a problem in such a way that it becomes trivial.

## Section A.

A1. Consider a family $\mathcal { A } = \{ A _ { 1 } , A _ { 2 } , . . . , A _ { n } \}$ of distinct subsets of some n-set X. Define a graph G on A with an edge between $A _ { i }$ and $A _ { j }$ if mod $A _ { i } \triangle A _ { j } = 1$ . If $A _ { i } \triangle A _ { j } = \{ x \}$ then we label the edge $A _ { i } A _ { j }$ with x. Prove that there is a forest $F \subset G$ whose edges include all the labels used on edges of G. Deduce that there exists some $x \in X$ for which all the sets $A _ { 1 } \setminus \left\{ x \right\} , A _ { 2 } \setminus \left\{ x \right\} , \ldots , A _ { n } \setminus \left\{ x \right\}$ are distinct.

A2. Prove that a tree T having 2k endvertices contains k edge-disjoint paths joining all the endvertices in pairs. Deduce if x is a vertex in a graph G with degree 2k and x is not a cutvertex of G then x is contained in k edge-disjoint cycles.

A3. Let x be a vertex of a graph G. For $r \geq 0$ define

$$
G _ { r } = G \left[ \{ y \in V ( G ) : d _ { G } ( x , y ) = r \} \right] .
$$

(In other words $G _ { r }$ is the subgraph of G induced by the vertices at distance r from x.) Prove that

$$
\chi ( G ) \leq \operatorname* { m a x } _ { r } \left( \chi ( G _ { r } ) + \chi ( G _ { r + 1 } ) \right) .
$$

A4. Prove that a tree T has a perfect matching if and only if the number of odd components in $G - v$ is 1 for every vertex v of G.

A5. In this question we consider directed graphs (digraphs) with no loops and no multiple edges (but we do allow both $\overrightarrow { x y }$ and $\overrightarrow { y x } )$ . A monotone tournament is an orientation of a complete graph in which (for some ordering of the vertices) the ordering on the edges is from the smaller to the larger vertex. A complete digraph is a digraph in which both $\overrightarrow { x y }$ and $\overrightarrow { y x }$ are edges for every x, y in its vertex set.

Given m ≥ 1 prove that if N is sufficiently large then every digraph on N vertices contains a subset of size m which induces either an empty digraph, a complete digraph, or a monotone tournament.

## Section B.

B1. A space $( X , \tau )$ is called extremally disconnected if the closure of every open set is open; that is, whenever $\mathcal { U } \in \mathcal { T }$ we have $\mathrm { c l } ( \mathcal { U } ) \in \mathcal { T }$ Show that in an extremally disconnected space, if $\mathcal { U } , \mathcal { V } \in \mathcal { T }$ and $\mathcal { U } \cap \mathcal { V } = \emptyset$ , then c $\begin{array} { r } { | ( \mathcal { U } ) \cap \mathrm { c l } ( \mathcal { V } ) = \emptyset } \end{array}$ (Hint: first show that $\mathcal { U } \cap \mathrm { c l } ( \mathcal { V } ) = \emptyset . )$

B2. A space $( X , \tau )$ is called locally path-connected if, for every $x \in X$ , every neighborhood of x contains a path-connected neighborhood of x. Show that a connected, locally pathconnected space is path-connected.

B3. Suppose that X is compact, Y is Hausdorff, $f : X \to Y$ is a continuous surjective map, and $g : Y  Z$ is a function. Show that if $g \circ f : X \to Z$ is continuous, then g is continuous.

B4. A space $( X , \tau )$ is called locally compact if, for every $x \in X$ and $x \in \mathcal { U } \in \mathcal { T }$ , there is a compact set $C \subseteq { \mathcal { U } }$ containing an open neighborhood of x. Show that the Cartesian product of two locally compact spaces is locally compact.