Do three of the questions from section A and four of the questions from section B. If you work more than the required number of problems, make sure that you clearly mark which problems you want to have counted. 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.

Question 1. A topological space X is locally compact if every point in X has an open neighborhood whose closure is compact. Show that the Cartesian product of two locally compact spaces, with the product topology, is also locally compact.

Question 2. Let X be the unit sphere in R 3 , and define an equivalence relation on X by

$$
( x , y , z ) \sim ( x ^ { \prime } , y ^ { \prime } , z ^ { \prime } ) \Leftrightarrow z = z ^ { \prime }
$$

Let $Z = X / { \sim }$ be the quotient space under this equivalence relation, with the quotient topology. Show that Z is homeomorphic to the interval $[ - 1 , 1 ]$ . (Here $\mathbb { R } ^ { 3 }$ and $[ - 1 , 1 ]$ have their usual topologies, and X has the subspace topology.)

Question 3. Show that if X is a Hausdorff space, and $A , B \subseteq X$ are disjoint, finite subsets of X, then there are disjoint open sets U , V in X with $A \subseteq { \mathcal { U } }$ and $B \subseteq \nu$

Question 4. Show that for a topological space X, if every $x \in X$ has an open neighborhood whose closure is a regular space, then X is regular.

Question 5. A topological space X is said to be contractible if the identity map $I _ { X } : X \to$ X is homotopic to a constant map $c : X \to X$ . Show that every contractible space is path-connected.

## Section B.

All graphs we consider are simple – that is they have no loops or multiple edges – and finite. A cubic graph is one that is 3-regular.

Question 6. Let $A _ { 1 } , A _ { 2 } , \ldots , A _ { n }$ be finite sets, and $d _ { 1 } , d _ { 2 } , \ldots , d _ { n }$ non-negative integers. Prove that there are disjoint subsets $D _ { i } \subset A _ { i }$ with $| D _ { i } | = d _ { i }$ if and only if for all $I \subset$ $\{ 1 , 2 , \ldots , n \}$ we have

$$
\left| \bigcup _ { i \in I } A _ { i } \right| \geq \sum _ { i \in I } d _ { i } .
$$

## Question 7.

a. Prove that every cubic 3 edge-connected graph is 3-connected.

b. Let us define a snarl as a graph that can be obtained from $K _ { 4 }$ by repeated applications of the operation of subdividing two edges and joining the two new vertices. Show that every snarl is 3-connected. (In fact it is true that every 3-connected cubic graph is a snarl.)

Question 8. Prove that every graph has a bipartition $V ( G ) = X \cup Y$ with the property that $e ( X , Y ) \geq e ( G ) / 2$ . Further, show that if G is cubic then we can achieve $e ( X , Y ) \geq$ $n ( G ) = 2 e ( G ) / 3$

## Question 9.

a. State the chromatic recurrence satisfied by the chromatic polynomial $\chi ( G ; k )$

b. Prove the for any graph G the number of acyclic orientations of G is $\chi ( G ; - 1 )$ . [An orientation of a graph G is an assignment of a direction to every edge of G. Such an orientation is acyclic if the resulting directed graph contains no directed cycles.]

## Question 10.

a. State Tur´an’s theorem concerning the maximum number of edges in a graph on n vertices not containing a $K _ { r }$

b. Prove that if G is a graph with $n \geq r + 1$ vertices and $t _ { r - 1 } ( n ) + 1$ edges then for every $n ^ { \prime }$ with $r \leq n ^ { \prime } \leq n$ there is a subgraph H of G with $n ^ { \prime }$ vertices and at least $t _ { r - 1 } ( n ^ { \prime } ) + 1$ edges. [Hint: consider a vertex in G of minimum degree.]

c. From the previous part deduce Tur´an’s theorem, and also the stronger fact that such a G contains two $K _ { r }$ subgraphs sharing $r - 1$ vertices.