Middle East Technical University Fall 2001 Math 341 Graph Theory

EXERCISES FOR MIDTERM I

Problem 1. Consider the skeletons of the 5 regular platonic polyhedra, that are the graphs formed by the vertices and edges of these polyhedra, and determine

(1) which ones are cubic graphs,

(2) which ones are Eulerian graphs,

(3) which ones are bigraph,

(4) which ones define a triangulation of a sphere (the surface of the polyhedron),

(5) what are the chromatic numbers for these graphs ?

(6) what are the edges chromatic numbers ?

(7) what are the maps (faces) chromatic numbers ?

Problem 2. Construct a graph Γ with 7 vertices which does not contain neither K_{3} nor K̄_{4}.

Problem 3. Give a list of all non-isomorphic spanning trees of Γ, where Γ is (1) K_{3,3},

(2) the skeleton of a cube.

Problem 4. Which of the following graphs are planar: K_{2,6}, K_{3,4}, K_{7}, K_{3,3,2}, K_{3,2,2} ?

Problem 5. How many edges and faces must contain a triangulation of a torus with 20 vertices ?

Problem 6. Find ex(10, K_{1,4}).

Problem 7. Sketch Ḡ and determine if it is a bigraph, where Γ is (1) the skeleton of a cube,

(2) K_{2,4}.

Problem 8. Prove that any graph contains a pair of vertices of the same degree (the graph should not contain loops of multiple edges).

Problem 9. Try to construct a pair of cubic graphs with 6 vertices which are (1) combinatorially non-equivalent,

(2) combinatorially equivalent, but not equivalent as plane graphs

(3) combinatorially equivalent, but not equivalent as graphs on a sphere.

Typeset by AMS-TEX