non bipartite random regular graph, degree can be fix, or grow slowly with n, do you believe it has simple spectrum? thanks

Yes, I believe that it will have simple spectrum for d >= 3 and it feels like something that should have been proved, though I can't actually find it. There is a loose association between automorphisms of a graph and multiple eigenvalues, and as most regular graphs have trivial automorphism group we lose this source of multiple eigenvalues. There are no other (frequently occurring) "reasons" for a graph to have multiple eigenvalues and so in general they won't be there. ADDED: Here are some exact numbers for connected (pairwise nonisomorphic) cubic graph: disconnected graphs vanish numerically and so we can ignore them. 10 vertices  19 graphs  6 with no repeated eigs = 31% simple 12 vertices  85 graphs  18 with no repeated eigs = 21% simple 14 vertices  509 graphs  316 with no repeated eigs = 62% simple 16 vertices  4060 graphs  2181 with no repeated eigs = 54% simple 18 vertices  41301 graphs  26446 with no repeated eigs = 64% simple (Actually this is growing more slowly than I expected... ) 


I guessed no but Gordon has changed my mind for degree greater than 2. If it has degree 2 it is a union of cycles. Eigenvalues are $2\cos(\frac{2 \pi j}{k})$ for various $ k$. In particular 2 has multiplicity the number of components. For random regular graphs of degree more than 2 I'd wildly guess that the eigenvalue behavior is like that of a large random symmetric matrix. This has been well studied, but not by me, all I know is the phrase "Gaussian Orthogonal Ensemble". Some experiments with degree 3 graphs suggest that with 30 vertices one component is highly likely and there is a repeated eigenvalue ( most often 0) about 2% of the time. At 60 vertices it is more like 0.2%. 


In 1986, Noga Alon conjectured in a Combinatorica article that, for any degree $d \ge 3$ and for any $\epsilon > 0$, most $d$regular graphs on $n$ vertices have all their eigenvalues except $\lambda_1=d$ bounded above by $2 \sqrt{d−1} + \epsilon$. In 2003, Joel Friedman established this conjecture: "A proof of Alon's second eigenvalue conjecture," 2003. Some further developments on the distribution of the eigenvalues are reported in a paper by Miller, Novikoff, and Anthony Sabelli, "The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs" in Experimental Mathematics, 2008. Perhaps some of these references will help. 

