Solution Wanted!
March 14, 2007
Exercises B.4-4
If v is reachable from k and k is reachable from u, then there are two paths. One is from k to v, another is from u to k. Then there must exist a path from u to v. So the relation is transitive. On the other hand, the graph is undirected, then the relation is symmetric. By the definition, v is reachable from v, so the relation is reflexive. Hence the relation is equivalence relation.
In directed graph, the property of reflexive and transitiverelation is hold.
Exercises B.4-3
For any graph G, add one edge decrease the number of connected components by at most one. If G has no edge, then after adding k edge G has at least n-k connected components. So we need to add at least |V|-1 edges to force G have just one connected component.
Exercises B.4-2
If path from u to v is not simple, then there is one vertex k such that appears in the path at least two times. We can remove all the vertex between k and another k (including another k but keep first k), it can decrease the number of k in the path at least one. Reapeat this process many times until can not find any repeat vertex, then the path is simple path from u to v.
Just like the above, we can remove reapeated vertices in the cycle. The only reapeated vertex in the cylcle is the start vertex and final vertex.
Exercises B.4-1
Because a edge (u,v) increase the degree of u and v by one, the summation of all vertices’ degree is double of edges.
