ALGORITHMIC PROOF OF MaxMult(T) = p(T)

Abstract

For a given graph $G$ we consider a set $S(G)$ of all symmetric matrices $A=[a_{ij}]$ whose nonzero entries are placed according to the location of the edges of the graph, i.e., for $i \ne j$, $a_{ij} \ne 0$ if and only if vertex $i$ is adjacent to vertex $j$. The minimum rank $\mr(G)$ of the graph $G$ is defined to be the smallest rank of a matrix in $S(G)$. In general the computation of $\mr(G)$ is complicated, and so is that of the maximum multiplicity $\MM(G)$ of an eigenvalue of a matrix in $S(G)$ which is equal to $n -\mr(G)$ where $n$ is the number of vertices in $G$. However, for trees $T$, there is a recursive formula to compute $\MM(T)$. In this note we show that this recursive formula for $\MM(T)$ also computes the path cover number $p(T)$ of the tree $T$. This gives an alternative proof of the interesting result, $\MM(T)=p(T)$.