METU Department of Mathematics Math 341 Graph Theory Fall 2008

MIDTERM I (PART I)

Problem 1 (7pts). Which of the following diagrams present (1) graphs

(2) multigraphs

(3) pseudo-graphs

(4) digraphs

(5) oriented graphs

(6) directed multigraphs

(7) none of the above

Problem 2. Which one of the following graphs is (1) a graph-path but not a cycle

(2) a graph-cycle

(3) a tree

(4) a forest

(5) a complete graph

(6) an Eulerian graph

(7) a bipartite graph.

Problem 3. Determine which ones of the following sequences of vertices in the graph sketched below are

(1) NOT walks

(2) closed walks

(3) walks but NOT trails

(4) Eulerian trails

(5) paths but NOT cycles

(6) Hamiltonian paths

(7) cycles. a) v_{1}v_{5}v_{1}

b) v_{1}v_{3}

c) v_{1}v_{3}v_{5}v_{1}

d) v_{1}v_{2}v_{4}v_{5}

e) v_{1}v_{2}v_{3}v_{4}v_{5}

f) v_{1}v_{2}v_{3}v_{1}v_{2}v_{3}v_{1}

g) v_{1}v_{3}v_{5}v_{1}v_{2}

Problem 4. Find the number of edges in the following graphs (1) K_{10},

(2) K_{7,8},

(3) \overline{K}_{5,6},

(4) dodecahedron (which has 20 trivalent vertices).

Problem 5. What is the eccentricity of a vertex of (1) K_{n}, n ≥ 2,

(2) K_{p,q}, p, q ≥ 2,

(3) the cube-graph (formed by the vertices and edges of a cube)

Problem 6. For the graph Γ shown below (1) sketch the subgraph induced by vertices {v_{1}, v_{3}, v_{4}, v_{5}};

(2) sketch three non-isomorphic spanning trees;

(3) find the dimension of the edge space E(Γ);

(4) find the dimension of the cycle space C(Γ);

(5) determine if the sum of all the edges of Γ is a cycle ? (explain);

(6) present a set of basic cycles;

(7) describe an Euler’s trail.

Problem 7. (1) Sketch the line graph L(K_{2,3}).

(2) What are the degrees of vertices of the line graph L(K_{p,q}) ?

(3) Prove that L(K_{p,q}) is not a bipartite graph for p, q ≥ 2, except one case. Find the exceptional case and the corresponding graph L(K_{p,q}).

(4) Prove that K_{2,3} is NOT a line graph L(Γ) for some graph Γ.

Problem 8. Sketch the clique graph (Γ) for the graph Γ from the problem 6.

Problem 9. (1) Find the characteristic sequence for the labelled tree sketched below.

(2) Find a tree with the following characteristic sequence 443322115.