Skip to main content
1 of 3

Prove: Random D-Regular Graph is an expander w/ prob >= 0.5

Context:

Many resources, like

http://math.mit.edu/~fox/MAT307-lecture22.pdf

state the threom in the general case, but then prove it only for the bipartite case.

The full case is supposedly proved in Pinkser's 1973 paper. However, I can't dig up a copy. Anyone know of a proof for the general case (i.e. d-regular, undirected, not-necessairly-bipartitite graph)?

Thanks!