Let us define the distance between two vertices in a graph to be the length of t

Question

Let us define the distance between two vertices in a graph to be the length of the shortest path between them. (The "length" is the number of edges in the path.) Let us further define the diameter of a graph to be the distance between the two vertices that are farthest apart. What is the diameter of the following graph? Prove that if every vertex in a graph is within distance n of a given vertex v, then the diameter of the graph is less than or equal to 2n. Are the following two graphs G_1 and G_2 isomorphic to each other? If so, please define an isomorphism between them; otherwise, please prove that there is none. G_1 with V_1 = {1, 2, 3, 4, 5, 6}, E_1 = {12, 23, 34, 14, 15, 35, 45}

Explanation / Answer

Answer 4:

Diameter 5 i.e. A->B->C->E->F->G

Answer 5:

Let v1,v2 are two vertices which are furthest apart i.e. distance between v1 and v2 is the diameter of the graph. Now since every vertix in graph is at distance <=n from v (Given) hence we can reach from v1 to v in <= n steps and v to v2 also in <=n steps therefore we can reach from v1 to v2 in <=2n steps. Proved

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.