I think this is false and there are many counterexamples. Here is a sage session. sage: ed,e=([(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)], (2, 4)) sage: G=Graph(ed);F=Graph(G);F.delete_edge(e) sage: G.adjacency_matrix().eigenvalues() [4, -1, -1, -1, -1] sage: F.adjacency_matrix().eigenvalues() [0, -1, -1, -1.645751311064591?, 3.645751311064591?]