1 Complete the proof from class by proving the second inequa

1. Complete the proof from class by proving the second inequality:

Theorem: For any connected graph G, rad(G) diam(G) 2 rad(G).

2.

Describe how you can use the adjacency matrix of a graph to determine

(a) the degrees of the vertices.

(b) if the graph is bipartite.

Solution

Solution : (1)

As rad(G) = minvV [maxuV dG(u, v)], so obviously rad(G) diam(G)
Now suppose that diam(G) goes from vertices d1 to d2, d1, d2 V .
Recall that rad(G) = minvV ecc(v).
Let the chosen v for minimal eccentricity be v.
Note that diam(G) dG(v, d1) + dG(v, d2).
Since diam(G) is the shortest path from d1 to d2,
any other path from d1 to d2 is either as long or longer.
Also note that dG(v, d1) + dG(v, d2) rad(G) + rad(G) = 2rad(G) since rad(G)
is the maximum distance of any other vertex from v in G.
Hence,rad(G) diam(G) 2rad(G)