Definition 0.2 Suppose that G = (V,E) is a connected graph. The diameter of G is...

Transcribed Image Text:

Definition 0.2 Suppose that G = (V,E) is a connected graph. The diameter of G is 8(G)= max d(x, y) x,yV 4. For this question assume that G is not a complete graph (a graph has 8(G) = 1 iff G is complete). (a) Suppose that G is a graph with 30 vertices, and every vertex has degree > 20. Show that 8(G)= 2. (b) More generally, suppose G is a graph with n 2 vertices. Find the lowest m such that if each vertex has degree >m, then (G) = 2. Give an example to show that lower m would not work. Definition 0.2 Suppose that G = (V,E) is a connected graph. The diameter of G is 8(G)= max d(x, y) x,yV 4. For this question assume that G is not a complete graph (a graph has 8(G) = 1 iff G is complete). (a) Suppose that G is a graph with 30 vertices, and every vertex has degree > 20. Show that 8(G)= 2. (b) More generally, suppose G is a graph with n 2 vertices. Find the lowest m such that if each vertex has degree >m, then (G) = 2. Give an example to show that lower m would not work.