METU Department of Mathematics Math 341 Graph Theory Fall 2008

MIDTERM II

Problem 1(5 pts). Which one of the following graphs (1) is NOT a block

(2) has NO Eulerian trail

(3) has a closed Eulerian trail

(4) has NO Hamiltonian path

(5) has a Hamiltonian cycle.

Problem 2(2 pts). Write down the relation between the minimal vertex degree δ(G) of a graph G, its connectivity κ(G) and its edge connectivity λ(G).

Problem 3(3 pts). Formulate Menger’s theorem (on connectivity of a graph).

Problem 4(5 pts). Find the minimal number of colors required to paint the faces (1) of a tetrahedron:

(2) of a cube:

(3) of an octahedron: so that faces with a common edge are colored differently ?

What is the minimal number of color that will be for sure enough to paint the faces of any polyhedron with n faces ?

Problem 5(2 pts). Explain briefly why every tree is 2-colorable.

Problem 6(2 pts). Assume that the vertices of graph G have degrees either 3 or 4. What can you say about the edge chromatic number, χ′(G), of G ?

Problem 7(1 pts). Formulate Euler’s formula for a polyhedron ?

Problem 8(5 pts). Give the numbers v of vertices, e of edges, and f of faces for the 5 regular polyhedra (Platonic solids)

(1) tetrahedron v =  e =  f =
(2) cube  v =  e =  f =
(3) octahedron v =  e =  f =
(4) dodecahedron v =  e =  f =
(5) icosahedron v =  e =  f =

Problem 9(5 pts). A polyhedron P has 20 triangular faces.

(1) Determine the number e = of its edges.

(2) Determine the number v = of its vertices.

(3) Determine the numbers f′ = e′ = v′ = of faces, edges and vertices of the polyhedron P′ dual to P.

Midterm II – part II

Problem 10(4 pts). Formulate at least 4 different conditions which are all equivalent to saying that graph G which has more than two vertices is a block.

Problem 11(4 pts). Prove that for any n, m ≥ 4 the bipartite graphs K_{n,m} has connectivity ≥ 4 ?

Problem 12(10 pts). Determine the connectivity κ, the chromatic number χ, and the edge chromatic number χ′ for

(1) tetrahedron-graph κ =  χ =  χ′ =
(2) cube-graph  κ =  χ =  χ′ =
(3) octahedron-graph κ =  χ =  χ′ =

Give your arguments. Formulate your guess (without giving arguments) about κ, χ, and χ′ in the case of dodecahedron and icosahedron.

Problem 13(4 pts). Construct an example of a trivalent graph with connectivity 2 and edge connectivity 3.

Problem 14(5 pts). For the graph Γ shown below (1) sketch the dual graph

(2) sketch a diagram in which region R_{1} becomes the infinity region

(3) sketch a diagram in which the top triangular becomes the infinity region (4) which polyhedron is represented by this graph ?

Problem 15(3 pts). Describe the 3-coloring of the edges corresponding to the 4-coloring of the map shown below.