METU Department of Mathematics Math 341 Graph Theory Fall 2008

EXERCISES FOR THE FINAL EXAM

Problem 1. Consider a regular tiling of an orientable surface of genus g, so that all vertices have degree n and all regions have degree m.

(1) Determine the number of vertices, edges and regions.

(2) What are the admissible values of n and m in the case g = 2 ?

Problem 2. Estimate from below the genus of an orientable surface admitting a realization of graphs (a) K_{n}; (b) K_{n,m}.

Problem 3. Determine the incidence and the adjacency matrices for the following graphs: (a) K_{4}, (b) K_{3,2}, (c) \overline{K}_{2,3}, (d) the cube-graph.

Problem 4. Find an oriented graph with the following groups of symmetries: (a) ℤ_{n}, (b) ℤ_{2} × ℤ_{2}, (c) ℤ_{3} × ℤ_{3}.

Problem 5. What is the group of symmetries of the following polyhedra P: (a) cube with a truncated vertex, (b) cube with a truncated edge, (c) tetrahedron with two truncated vertices, (d) cube with two truncated vertices (consider different mutual position of the two vertices).

Problem 6. Find the order of the group of symmetries for the following graphs (1) K_{n,n},

(2) K_{n} + K_{n} + K_{n} (disjoint union of three copies of K_{n}),

(3) disjoint union of two octahedron-graphs.

Problem 7. Find generators of (a) ℤ_{2n} (b) 𝔻_{n} so that the corresponding Cayley graph is K_{n,n}. Compare the orientations of the edges. (Start with the case n = 3). Explain why K_{n,m} cannot be the Cayley graph for some group G and some set of it generators?

Problem 8. Let Γ_{G} be the Cayley graph of a group G generated by 3 involutions. Prove that the edges of Γ_{G} are 3-colorable.

Problem 9. Find a group and its generators so that the Cayley graph is (a) tetrahedron, (b) K_{5}, (c) cube-graph, (d) octahedron-graph (ignoring the directions of the edges).

Problem 10.

(1) Give a list of all triangulations of a hexagon.

(2) Sketch the dual binary trees.

(3) Fix a base (some edge) of the hexagon and put brackets in the product “abcde” corresponding to each of the triangulations.

Problem 11. Determine the number of vertices and faces of degrees 3, 4, etc., and the number of edges for (a) associahedron, (b) permutohedron, (c) football polyhedron. Sketch the planar graphs of these polyhedra.

Problem 12. Prove or disprove existence of a symmetry of an associahedron-graph which

(1) rotates it quadrilateral face;

(2) rotates it pentagon face;

(3) transpose two quadrilateral faces.

Problem 13.

(1) Verify that the midpoint of the edges of a tetrahedron are the vertices of an octahedron.

(2) Prove or disprove that the midpoint of the edges of a cube are the vertices of an icosahedron.

Problem 14. Find planar graph diagrams of the five truncated regular polyhedra.

Problem 15. Is it possible to truncate five edges of a dodecahedron and obtain a polyhedron whose faces have degree ≤ 6 ?

Problem 16. Prove or disprove that the volleyball-graph is isomorphic to the permutohedron-graph.

Problem 17^{∗}. Determine the Coxeter graph of the symmetry group of the tiling in Problem 1.

Problem 18^{∗}. Show that the group of symmetries G = Sym(K_{3,3}) is a Coxeter group (present a set of involutions and verify that they generate G). Find the Coxeter graph for a minimal set of generating involutions.

Problem 19^{∗}. Sketch the Cayley graphs for the complete symmetry groups of the five regular polyhedra (tetrahedron, cube, octahedron, icosahedron and dodecahedron).