Ramanujan Graph - Extremality of Ramanujan Graphs

Extremality of Ramanujan Graphs

For a fixed and large, the -regular, -vertex Ramanujan graphs minimize . If is a -regular graph with diameter, a theorem due to Nilli states

Whenever is -regular and connected on at least three vertices, and therefore . Let be the set of all connected -regular graphs with at least vertices. Because the minimum diameter of graphs in approaches infinity for fixed and increasing, Nilli's theorem implies an earlier theorem of Alon and Boppana which states