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?$
$\begingroup$
$\endgroup$
4
-
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 PetrovDec 29, 2017 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 SinghDec 29, 2017 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 PetrovDec 29, 2017 at 8:24
-
$\begingroup$ Yes exactly, I am stuck in the same situation. $\endgroup$– Ranveer SinghDec 29, 2017 at 8:55
Add a comment
|