Tutorial 5

1. Recall that degree(v) is the number of edges incident at a
vertex v. Prove the following theorem: There is an eulerian-trail
in a graph G if and only if there are atmost 2 vertices of odd
degree.

2. A graph is called bipartite if the vertex set V is the disjoint
union of V_1 and V_2, such that every edge e=(v_1 ,v_2 ) of E must
be such that v_1 \in V_1 and v_2 \in V_2 . Prove the following
theorem: A graph is bipartite if and only if it contains no cycle
of odd length.

3. Let G be a graph such that there is a unique path between any
two vertices. Show that it is a tree. 

4. Write algorithms to compute the connectivity equivalence
relation on $V$ and $E$ of a graph. In other words, write an
algorithm, which when input two vertices, answers whether they are
related. Similarly, for the edge-connectivity equivalence
relation. How much time, in terms of |V| and |E| do your
algorithms take?

5. For a graph G(V,E), the distance d(v,w), between vertices v and
w, is the length of the shortest path between v and w. Show that
for any vertices v,w,x, we have the triangle law:
d(v,w)+ d(w,x) \geq d(v,x).
The diameter of a graph is the maximum of the distances between
two vertices. Give examples of graphs with very large and very
small diameters.