METU Department of Mathematics Math 341 Graph Theory Fall 2008

EXERCISES FOR MIDTERM II

Problem 1. Find the connectivity and edge connectivity of K_{3,4}. Find its chromatic number and edge chromatic number.

Problem 2. Find an example of a graph with vertices of degree ≥ 4 which has connectivity 2 and edge connectivity 3.

Problem 3. (1) Assume that for some pair of vertices a and b of a graph G there exist a path from a to b which passes through any given vertex v (different from a and b). Does it imply that there exist two disjoint trails connecting a and b ?

(2) Assume that for any pair of vertices v and w (different from a and b) there exists a path from a to b which passes through v and w. Does it imply existence of two disjoint paths connecting a and b ?

(3) Formulate some other condition(s) equivalent to existence of two disjoint paths connecting a and b.

Problem 4. About polyhedron P it is known that it has 10 triangular, 6 quadrilateral, and 4 pentagon faces. Determine the number of edges and vertices of P. Prove that P has a vertex of degree 3.

Problem 5. Assume that P is a convex polyhedron whose vertices and faces have all the same degree n. Find all possible values of n.

Problem 6. Prove that every convex polyhedron has a face of degree ≤ 5 and a vertex of degree ≤ 5.

Problem 7. Sketch a planar diagram of K_{4} and describe a 3-coloring of its edges, with colors i, j, k. Find the corresponding coloring of the map with colors 1, i, j, k, so that the infinity region has color ”1”.

Problem 8. Prove that the edges of a Hamiltonian trivalent graph are 3-colorable.

Problem 9. Find an example of a tree-valent graph whose edges are not 3-colorable.

Is it correct that every three-valent graph is four-colorable ? (Explain why, or disprove).^{∗}^{1}

Problem 10. Prove that the line graph L(K_{4}) is isomorphic to the octahedrongraph. Find a similar polyhedron whose graph is isomorphic to L(K_{2,3}). Determine the connectivity and the chromatic numbers of these graphs.

Problem 11^{∗}. Determine if the graphs L(K_{5}) and L(K_{3,3}) are planar ? Determine their connectivity and chromatic numbers.

Problem 12^{∗}. Prove or disprove that any polyhedron-graph is 3-connected.

1”∗” means a relatively difficult problem, harder than the exam questions