1. MULTIPLE CHOICE QUESTIONS

1. Consider the following two graphs:

G =  1  2  3  4  5  6  7 ,    H =

Select all of the following which are true.

(a) The graph G is a tree

(b) Both graphs have an odd number of connected components

(c) The graph G is a subgraph of H

(d) There is a homomorphism from G to H

2. Consider the following polygonal form of a surface:

=

c

Select all of the following which are true.

(a) The polygonal decomposition has two free edges

(b)  is homeomorphic to D2 # T

(c) s is non-orientable

(d) The surface has one puncture in standard form

3. Consider the following polygonal form of a surface:

 a          h    

b                               h   

c                                            g

s =                                          

d                                    f  

f

Select all of the following which are true.

(a) The Euler characteristic of s is −1

(b) In standard form the surface s has no cross-caps

(c) In standard form the surface s has no handles

(d) In standard form the surface s has no punctures

4. Markström’s graph is

=

Select all of the following which are true.

(a) The Euler characteristic of G is −6

(b) The graph G is planar

(c) The graph G can be embedded into the projective plane

(d) Every coloring of the faces of G needs at least five colors

5. Let K and K′ denote the following two knots:

,    K′ =

Select all of the following which are true.

(a) The two knots are homeomorphic

(b) The knot K′ is three colorable

(c) The knot K′ has 12 different five colorings

(d) The knot K has genus zero

6. Let K be the knot

=

Select all of the following which are true.

(a) The knot diagram is alternating

(b) The knot is alternating

(c) The genus of the knot is strictly bigger than zero

(d) The knot K is the unknot

8.

(a) Draw a complete bipartite graph with 5 vertices.

(b) Show that the complete bipartite graph K2,n is planar for all n ∈ N

9.

(a) Show that the number of 3-colorings is invariant under the first Reidemeister move.