I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ will be $n-1$.

now I want to say an example to show that it is possible to remove one vertex and the multiplicity of one of eigenvalue rise,but I couldn't,it will be great if you help me with this,thanks.


Consider $C_{3} \cup C_{3} \cup K_{4}$. We have an eigenvalue $\lambda = 2$ with multiplicity two. Removing a vertex from $K_{4}$ yields $C_{3}$, thus increasing the multiplicity of $\lambda = 2$ to three.

  • $\begingroup$ thanks,I didn't think this way,if we want to have a connected example,can we have one? $\endgroup$ – kpax Dec 23 '14 at 6:31
  • $\begingroup$ $C_3$ is 2-regular,and its biggest eigenvalue is 2,so you mean that the multiplicity of $\lambda=2$ increase,am I right? $\endgroup$ – kpax Dec 23 '14 at 6:37
  • $\begingroup$ That's correct. Serves me right for posting late at night! :-) I can't think of a connected example, but I'm no expert with spectral graph theory. Sorry I can't be of more help! $\endgroup$ – ml0105 Dec 23 '14 at 6:39
  • $\begingroup$ thanks a lot,it was so helpful for me,thank you for answering my question. $\endgroup$ – kpax Dec 23 '14 at 6:43
  • 1
    $\begingroup$ The graph on five vertices got by joining a new vertex to one vertex on the the 4-cycle is a connected example. Its eigenvalues are simple and there are three vertices you can delete. $\endgroup$ – Chris Godsil Dec 23 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.