Editing Spectral graph theory (section)

===Cheeger inequality===
When the graph ''G'' is ''d''-regular, there is a relationship between ''h''(''G'') and the spectral gap ''d'' − λ<sub>2</sub> of ''G''. An inequality due to Dodziuk<ref>J.Dodziuk, Difference Equations, Isoperimetric inequality and Transience of Certain Random Walks, Trans. Amer. Math. Soc. 284 (1984), no. 2, 787-794.</ref> and independently [[Noga Alon|Alon]] and [[Vitali Milman|Milman]]{{Sfn|Alon|Spencer|2011}} states that<ref>Theorem 2.4 in {{harvtxt|Hoory|Linial|Wigderson|2006}}</ref>

: <math>\frac{1}{2}(d - \lambda_2) \le h(G) \le \sqrt{2d(d - \lambda_2)}.</math>

This inequality is closely related to the [[Cheeger bound]] for [[Markov chains]] and can be seen as a discrete version of [[Cheeger constant#Cheeger.27s inequality|Cheeger's inequality]] in [[Riemannian geometry]].

For general connected graphs that are not necessarily regular, an alternative inequality is given by Chung<ref name=chung>{{cite book |last1 =Chung |first1 =Fan |author-link =Fan Chung |year =1997 |title =Spectral Graph Theory |isbn =0821803158 |mr =1421568 |url =http://www.math.ucsd.edu/~fan/research/revised.html |postscript = [first 4 chapters are available in the website] |editor =American Mathematical Society |publisher =Providence, R. I.}}</ref>{{rp|35}} 
:<math> \frac{1}{2} {\lambda} \le {\mathbf h}(G)  \le \sqrt{2 \lambda},</math>
where <math>\lambda</math> is the least nontrivial eigenvalue of the normalized Laplacian, and <math>{\mathbf h}(G)</math> is the (normalized) Cheeger constant  
:  <math> {\mathbf h}(G) = \min_{\emptyset \not =S\subset V(G)}\frac{|\partial(S)|}{\min({\mathrm{vol}}(S), {\mathrm{vol}}(\bar{S}))}</math>
where <math>{\mathrm{vol}}(Y)</math> is the sum of degrees of vertices in <math>Y</math>.