Let G be a connected graph. For two vertices u and v. define d(u, u) to be the l

Question

Let G be a connected graph. For two vertices u and v. define d(u, u) to be the length of the shortest path in G from u to v: we say that d(u. v) is the distance from it to v. Note that d(u. u) = 0 as the path it is considered to be a path of length 0 from u to u. The diameter of G. denoted diam(G), is the maximum distance between any pair of vertices in G. Specifically, diam(Cs) = max d(u, v). u, u v Prove that for any connected G = (V, E). diam(G) le V - 1. (Hint: Suppose that there is a path - in which some vertices may appear more than once - from u and v. How can you find a simple path between u and v? What is the length of the longest simple path in G?)

Explanation / Answer

|E| =(1) sum { |Ei| } >=(2) sum{|Vi|-1} =(3) |V| - sum{1 | for each Ci} =(4) |V| - #components -> |E| >= |V| - #components #components >= |V| - |E|

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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