Do seven questions. Of these at least three should be from section A and at least three 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. Standard results from the courses may be used without proof provided they are clearly stated. 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. Prove that a connected graph on n vertices has n edges if and only if it contains exactly one cycle.

b. Let $n \geq 3$ and suppose that G is an n vertex graph with the property that for all $v \in V ( G )$ the graph $G \setminus \{ v \}$ is a tree. Determine the number of edges in G, and thereby determine G.

Question 2. Prove that if G is a k-connected graph and $S , T \subset V ( G )$ are disjoint subsets of vertices, each of size k, then it is possible to find k disjoint paths $P _ { 1 } , P _ { 2 } , \ldots , P _ { k }$ in G and labelings $S = \{ s _ { 1 } , s _ { 2 } , \ldots , s _ { k } \} , T = \{ t _ { 1 } , t _ { 2 } , \ldots , t _ { k } \}$ such that Pi is a path from si to ti $s _ { i }$ $t _ { i }$

Question 3. Prove that every planar graph G has $\chi ( G ) \leq 5$

Question 4. Suppose that X is a set of size mn and $( A _ { i } ) _ { 1 } ^ { m } , ( B _ { i } ) _ { 1 } ^ { m }$ are partitions of X into m sets of size n. Prove that one can renumber the sets $B _ { i }$ in such a way that $A _ { i } \cap B _ { i } \neq \emptyset$ for $i = 1 , 2 , \dots , m$

## Question 5.

a. State Tutte’s Theorem concerning graphs having a 1-factor.

b. Prove that every connected, bridgeless, 3-regular graph has a 1-factor.

c. Find a connected 3-regular graph with no 1-factor.

## Section B.

Question 6. Suppose that $d , d ^ { \prime }$ are metrics on the set X with $d ( x , y ) \leq d ^ { \prime } ( x , y )$ for every $x , y \in X$ . Show that the metric topology $( X , d )$ is coarser than the metric topology $( X , d ^ { \prime } )$ •

Question 7. A toplogical space $( X , \tau )$ is called limit-point compact if every infinite subset A of X has a limit point. Show that every closed subset of a limit-point compact space is limit-point compact.

Question 8. Let $S ^ { 1 } \subseteq \mathbb { R } ^ { 2 }$ denote the unit sphere (with the subspace topology), and R the real line with the usual topology. Show that for every continuous map $f : S ^ { 1 } \to { \mathbb { R } }$ there is an $x \in S ^ { 1 }$ with $f ( x ) = f ( - x )$

Question 9. Let $\tau , \tau ^ { \prime }$ be two topologies on X. Show that if $( X , \tau )$ is compact and Hausdorff, $\mathcal { T } \subseteq \mathcal { T } ^ { \prime }$ , and $\mathcal { T } \neq \mathcal { T } ^ { \prime }$ , then $( X , T ^ { \prime } )$ is Hausdorff but not compact.

Question 10. Recall that a topological space X is locally connected if for every point $x \in X$ and every neighbourhood U of x there exists a connected neighbourhood V of x with $V \subseteq U$ a. Prove that a topological space X is locally connected iff for every open set $U \subseteq X$ the components of U are open. Now let $p : X \to Y$ be a quotient map.

b. Prove that if C is a component of an open subset $U \subseteq Y$ then $p ^ { - 1 } ( C )$ is a union of components of $p ^ { - 1 } ( U )$

c. Deduce that if X is locally connected then so is Y .