Middle East Technical University Fall 2001 Math 341 Graph Theory

MIDTERM I, PART II

NOVEMBER 3, TIME: 40 MIN

Name, ID, the signature: ——————————————————————————————————–

|  1  2  3  4  5  |  Σ  |

——————————————————————————————————–

Problem 1. (10 pts) (1) Sketch 3 non-isomorphic spanning subtrees of K_{2,5} and

(2) determine the combinatorial invariants of these subtrees which show that these subtrees are not isomorphic,

(3) explain why a path-tree cannot be a spanning subtree of K_{2,5},

Problem 2. (10 pts) Determine for the graph G below (1) the chromatic number of G

(2) edges’ chromatic number of G

(3) map’s chromatic number of G Indicate the coloring in each case and briefly comment why it is minimal. Sketch the dual graphs for G and F

Problem 3. (10 pts) For the graph G in Problem 2

(1) find a pair of topologically non-equivalent graph diagrams of G in a sphere S^{2};

(2) sketch the dual graphs for this pair of diagrams;

(3) find a pair of topologically non-equivalent diagrams of G on a plane ℝ^{2}, which become equivalent in a sphere S^{2} after identification ℝ^{2} ≅ S^{2} − {pt}.

Problem 4. (10 pts)

(1) Sketch K_{3,4} in ℝP^{2} indicating the faces

(2) Prove that K_{4,4} cannot be sketched in ℝP^{2}

Problem 5. (10 pts) G is a regular graph on a torus, such that all the vertices have the same degree d and all the faces are bounded by the same number m of edges. Determine, what can be the values of d and m ?

Typeset by AMS-TEX