METU Department of Mathematics Math 341 Graph Theory Fall 2008

FINAL

Problem 1(2 pts).

(1) Formulate the Ramsey theorem about subgraphs in K_{6}.

(2) Give a definition of the Ramsey number r(m, n).

Problem 2(1 pts). What is the maximal number of edges that can be in a graph with 10 vertices so that it does not contain triangles (subgraphs K_{3}) ?

Problem 3(1 pts). Formulate Euler’s formula for orientable surfaces of genus g.

Problem 4(2 pts). Mark the correct statements below:

(1) There exists a planar diagram of K_{5}.

(2) There exists a torus diagram of K_{6}.

(3) There exists a torus diagram of K_{7}.

(4) There exists a torus diagram of K_{8}.

Problem 5(4 pts). Give a list of matrices (if any) which are (1) incidence matrices of some graphs

(2) incidence matrices of pseudo-graphs, but not of graphs

(3) adjacency matrices of some graphs

(4) adjacency matrices of directed graphs, but not of usual graphs

(5) adjacency matrices of weighted graphs, but not of usual graphs.

A = ( \begin{matrix}1 & 1 \\ 1 & 1 \end{matrix} ), B = ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ), C = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ), D = ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ), E = ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} ).

Problem 6(4 pts). Find the following groups of symmetries (1) Sym(K_{5})

(2) Sym(K_{2,2})

(3) Sym(K_{4,5})

(4) group of rotations of a tetrahedron

(5) group of rotation of a cube

Problem 7(4 pts). Determine the order of the following groups (1) group of symmetries of K_{3,3}

(2) group of symmetries of K_{4} + K_{4} + K_{3} (the graph with 3 components: two components are K_{4} and one component is K_{3})

(3) group of rotations of a cube

(4) the complete group of symmetries of an octahedron.

Problem 8(3 pts). Sketch the Cayley graph of (1) ℤ_{6} with generator 1

(2) ℤ_{7} with two generators, 2 and 3

(3) ℤ_{2} × ℤ_{2} with generators (1, 0) and (0, 1).

Problem 9(2 pts). Sketch the binary trees corresponding to the products (1) ((ab)(cd))(ef)

(2) ((ab)c)((de)f)

Problem 10(3 pts).

(1) Give a formula for the number of binary trees with a root and n leaves ? Calculate this number for n = 5.

(2) Give a formula for the number of triangulations of an n-gon ? Calculate this number for n = 8.

Problem 11(2 pts). Sketch a binary rooted tree corresponding to the triangulation of a polygon with a marked edge (the base) shown below. Put brackets in the product abcdefg corresponding to this binary tree.

Problem 12(3 pts). Sketch a planar graph diagram of (1) a truncated tetrahedron

(2) a cube with four parallel truncated edges

(3) a dodecahedron Problem 13(1 pts). Find the angles of the spherical faces of a spherical cube.

Problem 14(1 pts). Find the area of a spherical triangle with angles α, β, γ.

Problem 15(3 pts). Sketch the Coxeter graphs of the following Coxeter groups. (1) permutation group S_{4}

(2) D_{5}

(3) ℤ_{2} × ℤ_{2}.

Problem 16(3 pts). Describe the Schläfli symbols of (1) a tetrahedron

(2) a cube

(3) an octahedron

(4) dodecahedron

(5) icosahedron

Problem 17(1 pts). Sketch the three regular tiling of a plane.

FINAL_{PART II}

Problem 18(5 pts). Assume that Γ is a trivalent graph on a surface of genus 3 such that all the regions are simply connected and have degree 7. Determine the number of vertices, regions and edges of Γ.

Problem 19(5 pts). Prove that graph K_{10} does not admit a diagram without self-intersection of edges on a surface of genus 2.

Problem 20(6 pts). Sketch graph K_{7} (1) on a flat torus.

(2) on a flat Klein bottle.

Problem 21(6 pts). Sketch a planar graph representing (1) icosahedron

(2) football-graph Determine the order of their complete symmetry groups.

Problem 22(6 pts). Give a list of the graphs and digraphs on the figure below (if any) which have a given group of symmetry

(1) ℤ_{2}

(2) ℤ_{3}

(3) ℤ_{2} × ℤ_{2}

(4) D_{3}

(5) D_{4}

(6) trivial group.

Problem 23(6 pts).

(1) Sketch a planar associahedron-graph. Find the numbers f_{3}, f_{4}, f_{5}, f_{6} of faces in an associahedron which have degrees respectively 3, 4, 5, 6.

(2) Do the same for permutohedron.

Problem 24(6 pts).

(1) Sketch the fundamental region for the complete group of symmetries of a spherical cube. Find the Coxeter graphs of this group of symmetries.

(2) Do the same for a spherical dodecahedron.