Diameter and low-degree vertex

  1. Let \(G = (V,E)\) be an undirected connected graph. Suppose \(G\) has a pair of nodes \(s,t\) that are distance \(d\) apart. Show that there is a vertex \(v\in G\) such that the degree of \(v\) is at most \(6n/d\) where \(n = |V|\).
  2. Show that for directed graphs the above is not true. More precisely, give an example of a directed graph on \(n\) nodes such that there is a pair of nodes \(s, t\) such that distance from \(s\) to \(t\) is \(\Omega(n)\) and for each node \(v\) in the graph, both the in-degree and out-degree are \(\Omega(n)\).

Related Content