Consider the following relation on the graph G. Let the graph have n vertices. Two vertices aand b are related if there is an edge between a and b. That is is a relation form V (G) to V (G)and for any a and b, a b if a has an edge to b. Assuming that the graph G is undirected and G hasa path P on all n vertices. Then give tight upper bound and lower bound on the number of edgesin the graph G if the relation is an equivalence relation. Prove the correctness of your answer.Assume that n is a large number.

Answer rating: 100% (QA)

ANSWER Prove that a graph with n vertices n1 edges and no circuit is a connected graph ... View the full answer