I hit a stone wall with this particular problem as graph coloring was not a topic covered in any of my courses. I would appreciate any help: Let G = (V, E) be a d-regular n-vertex graph that is 3-colourable and such that there is a 3-colouring in which the colour classes have equal size |V |/3. Let A be the adjacency matrix and L be the Laplacian of G given by L = I − 1/d A .
Let $$λ_1 ≤ λ_2 ≤ · · · ≤ λ_n$$ be the eigenvalues of the Laplacian.
1)Prove that L has at least two eigenvalues which are greater than or equal to 3/2,that is, λn−1 ≥ 3/2
2) Then there should be given an example in which the bound the tight.
3) Finally we must show that the converse is not true.