Let $G$ be an undirected graph with a vertex $v$ having degree 1. Let $G_1$ be the induced subgraph of $G$ after removing $v$, and $G_2$ be the induced graph of $G$ after removing $v$ along with its adjacent vertex. Let $\phi(G)$ denote the characteristic polynomial (corresponding to the adjacency matrix) of $G$. It is well known that $$\phi(G)=\lambda\phi(G_1)-\phi(G_2).$$ Using the above relation how can we prove that the nullity (number of zero eigenvalues) of $G$ equals to the nullity of $G_2?$

  • 1
    $\begingroup$ Why do you ask about proving with this relation? It looks easier to prove without it: nullity is the number of vertices minus the rank (of adjacency matrix), and the rank of $G$ equals rank of $G_2$ plus 2, this is clear by elementary operations (subtracting the rows and columns corresponding to $v$). $\endgroup$ – Fedor Petrov Dec 29 '17 at 7:51
  • $\begingroup$ Yes that I know. But I want the result from characteristic polynomial only. The above relation is also true for directed graph, and I want to know the number zero eigenvalues in that case using the number of zero eigenvalues in the subgraphs. $\endgroup$ – Ranveer Singh Dec 29 '17 at 8:15
  • 1
    $\begingroup$ This relation shows that $null(G)\geqslant null(G_2)$, and equality holds unless $null(G_2)=1+null(G_1)$ and the corresponding coefficients are equal (we always have $1+null(G_1)\geqslant null(G_2)$). But I do not see immediately how to provу that they are not equal in this case. $\endgroup$ – Fedor Petrov Dec 29 '17 at 8:24
  • $\begingroup$ Yes exactly, I am stuck in the same situation. $\endgroup$ – Ranveer Singh Dec 29 '17 at 8:55

Your Answer

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

Browse other questions tagged or ask your own question.