Middle East Technical University Fall 2001/2002 Math 341 Graph Theory

FINAL

JANUARY 12, TIME: 100 MIN

Problem 1. (18 pts)

(1) Prove that every edge in a tree is a bridge

(2) Which vertices in a tree are cut-points ? Explain the reasons.

(3) Justify that every tree is a bipartite graph.

Problem 2. (20 pts)

(1) Show that the edge connectivity of any Hamiltonian graph is ⩾ 2.

(2) Show that the edge connectivity of any cubic graph is ⩽ 3.

(3) Construct a Hamiltonian cubic graph with the edge connectivity 2.

Problem 3. (20 pts) For the graph Γ shown below (1) Describe the group Aut(Γ) of symmetries of Γ.

(2) What is the order of this group ? (Motivate your answer).

(3) Show how is the vertex set of Γ split into orbits with respect to the action of Aut(Γ). What is the number of different orbits ?

Problem 4. (16 pts)

(1) For the curve below sketch a Chord Diagram

(2) Sketch a regularly immersed curve in ℝ^{2} with the Chord Diagram shown below.

Problem 5. (16 pts) Sketch (1) a rooted tree for the tree-like curve T below.

(2) a tree-like curve corresponding to the rooted tree R below.

Problem 6. (16 pts)

(1) Find the (dual) face graph for the following curve C (taking into account the infinite face).

(2) Show the chess-board shading for the curve C and sketch the corresponding graph.

Problem 7. (24 pts) Assume that X(G, C) is a (non-directed) Cayley graph and C = {a, b, c}, where a = a^{−1}, b = b^{−1} and c = c^{−1} are three distinct elements generating group G. Answer the following questions giving a briefly your reasons.

(1) What are the degrees of the vertices of the graph X(G, C) ?

(2) How many vertices and edges may contain graph X(G, C), if |G| = n ?

(3) Is graph X(G, C) necessarily connected ?

(4) Prove that the edges of X(G, C) are 3-colorable.

Typeset by AMS-TEX