Is it true that, for a tree, rank of adjacency matrix is equal to twice the matching number?

Question

Is it true that, for a tree, rank of adjacency matrix is equal to twice the matching number?

At least in case of trees with perfect matchings, the answer is yes, since they are of full rank.

Answer 1

Yes. It is true. Books on graph spectral theory will usually contain a proof. The simplest argument rests on a formula for the characteristic polynomial. Suppose $G$ and $H$ are vertex-disjoint graphs and $a$ and $b$ are vertices in $G$ and $H$ respectively. Let $X$ be the graph we get by adding an edge joining $a$ to $b$. Using $\phi$ to denote the characteristic polynomial, we have \[ \phi(X,t) = \phi(G,t)\phi(H,t) -\phi(G\setminus a,t)\phi(H\setminus b,t) \] Given this it is easy to establish your result for trees (or forests), by induction.

The identity itself can be proved using determinant expansions.